文章目錄

• T1：小P的lol
• • title
  • solution
  • code
• T2：創(chuàng)世紀(jì)
• • title
  • solution
  • code
• T3：無聊的數(shù)對
• • title
  • solution
  • code

T1：小P的lol

title

solution

此題非常水…
先用素?cái)?shù)篩，篩出$[1,n]$中的質(zhì)數(shù)
質(zhì)數(shù)越小，倍數(shù)的分布就越密集
所以質(zhì)數(shù)一定是從小開始往大的取
然后就是暴力跑，考試的時(shí)候我以為暴力會(huì)$T$，一直在思考打容斥，幸好最后交的是暴力，嘻嘻~

code

#include <cstdio> #define MAXN 10000005 int n, k, cnt, ans; int prime[MAXN]; bool vis[MAXN], flag[MAXN];void init() {for( int i = 2;i <= n;i ++ ) {if( ! vis[i] ) {vis[i] = 1;prime[++ cnt] = i;}for( int j = 1;j <= cnt && i * prime[j] <= n;j ++ ) {vis[i * prime[j]] = 1;if( i % prime[j] == 0 ) break;}} }int main() {scanf( "%d %d", &n, &k );init();if( k == n - 1 ) return ! printf( "%d", cnt );for( int i = 1;i <= cnt;i ++ ) {for( int j = prime[i];j <= n;j += prime[i] ) {if( flag[j] == 0 ) {flag[j] = 1;ans ++;if( ans >= k ) return ! printf( "%d", i );}}}return 0; }

T2：創(chuàng)世紀(jì)

title

applepi手里有一本書《創(chuàng)世紀(jì)》，里面記錄了這樣一個(gè)故事……

上帝手中有著N 種被稱作“世界元素”的東西，現(xiàn)在他要把它們中的一部分投放到一個(gè)新的空間中去以建造世界。每種世界元素都可以限制另外一種世界元素，所以說上帝希望所有被投放的世界元素都有至少一個(gè)沒有被投放的世界元素能夠限制它，這樣上帝就可以保持對世界的控制。
由于那個(gè)著名的有關(guān)于上帝能不能制造一塊連自己都不能舉起的大石頭的二律背反命題，我們知道上帝不是萬能的，而且不但不是萬能的，他甚至有事情需要找你幫忙——上帝希望知道他最多可以投放多少種世界元素，但是他只會(huì)O(2^N) 級別的算法。雖然上帝擁有無限多的時(shí)間，但是他也是個(gè)急性子。你需要幫助上帝解決這個(gè)問題。

輸入格式
第一行是一個(gè)整數(shù)N，表示世界元素的數(shù)目。
第二行有 N 個(gè)整數(shù)A1, A2, …, AN。Ai 表示第i 個(gè)世界元素能夠限制的世界元素的編號。

輸出格式
一個(gè)整數(shù)，表示最多可以投放的世界元素的數(shù)目。

樣例
樣例輸入
6
2 3 1 3 6 5
樣例輸出
3

數(shù)據(jù)范圍與提示
樣例說明
選擇2、3、5 三個(gè)世界元素即可。分別有1、4、6 來限制它們。

數(shù)據(jù)范圍與約定
對于30% 的數(shù)據(jù)，N≤10。
對于60% 的數(shù)據(jù), N≤10^5。
對于 100% 的數(shù)據(jù)，N≤10^6，1≤Ai≤N，Ai≠i。

solution

貪心
考場上通過找規(guī)律我發(fā)現(xiàn)了
環(huán)的點(diǎn)大小為奇數(shù)，產(chǎn)生的貢獻(xiàn)是$cnt>>1$
環(huán)的點(diǎn)大小為偶數(shù)，產(chǎn)生的貢獻(xiàn)還是$cnt>>1$

通過輸入的要求，可以知道最后圖一定是以鏈+環(huán)的形式
先處理鏈的形式，每兩個(gè)綁一起產(chǎn)生1的貢獻(xiàn)，可以類似拓?fù)淙ヅ?br /> 但是鏈與環(huán)的交接處那個(gè)點(diǎn)是在環(huán)的時(shí)候去產(chǎn)生貢獻(xiàn)，不要在鏈的時(shí)候搞
最后跑出環(huán)的大小，計(jì)算貢獻(xiàn)

code

#include <cstdio> #define MAXN 1000005 int n, l = 1, r, ans; int v[MAXN], d[MAXN], st[MAXN]; bool vis[MAXN];int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) {scanf( "%d", &v[i] );d[v[i]] ++;}for( int i = 1;i <= n;i ++ )if( ! d[i] ) st[++ r] = i;while( l <= r ) {if( ! vis[st[l]] && ! vis[v[st[l]]] ) {ans ++;vis[v[st[l]]] ++;if( -- d[v[v[st[l]]]] == 0 )st[++ r] = v[v[st[l]]];}vis[st[l ++]] = 1;}for( int i = 1;i <= n;i ++ )if( ! vis[i] ) {int cnt = 0, j = i;while( v[j] != i )vis[j] = 1, j = v[j], cnt ++;vis[j] = 1;ans += ( cnt + 1 ) >> 1;}printf( "%d", ans );return 0; }

T3：無聊的數(shù)對

title

solution

要求$i?j=k$中$k$的二進(jìn)制中1的個(gè)數(shù)為奇數(shù)
此時(shí)$i,j$的要求是一奇一偶

證明如下：

先溫習(xí)一下二進(jìn)制的異或法則
$1?1=0$
$0?0=0$
$1?0=1$

①
如果$i,j$二進(jìn)制的第$p$位不相等，有一個(gè)為$1$，異或后還是$1$
$1$的個(gè)數(shù)奇偶性不改變
②
如果相等
1）兩個(gè)都為$0$，異或?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$0$，也不會(huì)對$1$的奇偶性造成改變
2）兩個(gè)都為$1$，那么異或后變成$0$，個(gè)數(shù)減掉$2$，奇偶性沒改變
綜上，$i,j$中$1$的奇偶性是永遠(yuǎn)不會(huì)改變的
奇數(shù)+奇數(shù)=偶數(shù)，偶數(shù)+偶數(shù)=偶數(shù)，奇數(shù)+偶數(shù)=奇數(shù)
所以必須要一奇一偶，證明完畢！

再觀$l,r$十分龐大，已經(jīng)超出$int$邊界
但是不要怕，靜態(tài)區(qū)間求個(gè)數(shù)之類的題，最喜歡丟線段樹上面了
我們就維護(hù)一棵線段樹，把區(qū)間操作丟上去
然后分別統(tǒng)計(jì)二進(jìn)制$1$為奇數(shù)的個(gè)數(shù)和二進(jìn)制$1$為偶數(shù)的個(gè)數(shù)
進(jìn)行乘法操作，直接用根的信息即可
注意： 被完全覆蓋的區(qū)間記得打懶標(biāo)記，因?yàn)檫@個(gè)區(qū)間被完全包含了，是不會(huì)產(chǎn)生新貢獻(xiàn)的

這道題其實(shí)也就這樣吧…

code

#include <cstdio> #define ll long long #define MAXN 100005 int n, cnt, root; ll l, r; //odd表示區(qū)間[l,r]內(nèi)二進(jìn)制中1為奇數(shù)的個(gè)數(shù) //even表示區(qū)間[l,r]內(nèi)二進(jìn)制中1為偶數(shù)的個(gè)數(shù) ll find( ll x ) {if( x & 1 ) return ( x + 1 ) >> 1;return ( x >> 1 ) + __builtin_parityll( x ); }bool flag[MAXN]; int lson[MAXN << 2], rson[MAXN << 2]; ll odd[MAXN], even[MAXN];void modify( int &t, ll l, ll r, ll L, ll R ) {if( flag[t] ) return;if( ! t ) t = ++ cnt;if( L <= l && r <= R ) {flag[t] = 1;odd[t] = find( r ) - find( l - 1 );even[t] = r - l + 1 - odd[t];return;}ll mid = ( l + r ) >> 1ll;if( L <= mid ) modify( lson[t], l, mid, L, R );if( mid < R ) modify( rson[t], mid + 1, r, L, R );odd[t] = odd[lson[t]] + odd[rson[t]];even[t] = even[lson[t]] + even[rson[t]]; }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) {ll l, r;scanf( "%lld %lld", &l, &r );modify( root, 1, ( 1ll << 32 ) - 1, l, r );printf( "%lld\n", odd[1] * even[1] );}return 0; }

終于時(shí)隔多年，我補(bǔ)完了完整的一場狂歡賽！！！

總結(jié)

以上是生活随笔為你收集整理的[帝皇杯day 1] [NOIP2018模拟赛]小P的loI（暴力+素筛），【NOIP模拟赛】创世纪（贪心），无聊的数对（线段树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。