今天有人品爆發，240分，但是第三題沒特判，第一題沒用高精度也是可以GG的……

明天就是NOIP了，高一黨就全當體會一下吧！（P.S.今天有兩個高一的來考試（不聽勸啊~），于是乎……但願沒影響到他們考試的心情）

每日推薦!

沒錯，這次的每日推薦就是遊戲王！！！

從國小二年級開始，我看見了遊戲王的起起伏伏，也經曆了從萌新到菜鳥，再到現在的一般的水準，用遊戲王作為我今年noip的最後一份推薦，就是想貫徹遊戲王決鬥中除強大的計算外更吸引我的精神，never give up！！

是以這次就以一句帥氣的話來告訴世界，高一黨有我在，而我也一定要創造奇迹！！！！（這flag立的………………）

than ：：所列哇多噶那！！！（千星大大快更新！！！！）

11月18日——離noip還有1天[遊戲王YGO]每日推薦!總結

第一題：信(believe.cpp/c/pas)

背景描述：

11月18日——離noip還有1天[遊戲王YGO]每日推薦!總結

一切死亡都有冗長的回聲

—— 《一切》北島

給定一個N個元素的序列A，

定義Bi = (Ai and A1) + (Ai and A2) + (Ai and A3)+ …… + (Ai and An)

定義Ci = (Ai or A1) + (Ai or A2) + … + (Ai or An)

求B和C序列。

輸入格式：

第一行一個整數N表示序列長度

接下來一行N個整數，第i個整數為Ai

輸出格式：

第一行N個整數輸出B序列

第二行N個整數輸出C序列

樣例輸入：

4

3 5 1 1

樣例輸出：

6 8 4 4

16 22 10 10

資料規模：

對于50%的資料， N <= 1000

對于100%的資料， N <= 100000， Ai <= 100000

注意事項：

輸入量較大，請使用比較快的例如scanf的讀入方式，最好不要采用cin。//使用讀入優化readin（）；注：template< class T >

思考與題解

第一題：

考慮每一位對每個數的貢獻，令cnt[i]為二進制第i位為1的數的個數。

如果第j個數，第i位為1，那麼第i位對Bj的貢獻為cnt[i] * (1 << i), 對Cj的貢獻為n * (1 << i)

否則，對Bj的貢獻為０, 對Cj的貢獻為cnt[i] * (1 << i)

複雜度N*logV, V代表值域

題解已經寫得很清晰了……小編就不再贅述了。

code

嗚嗚嗚~~沒有标答快……

#include<set>
#include<list>
#include<deque>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
#include<map>
#define Li(x) x<<1
#define Ri(x) x<<1|1
#define clr(x) memset((x),0,sizeof(x))
#define cld(x) memset((x),127/2,sizeof(x))
#define smin(x,y) x=min(x,y)
#define smax(x,y) x=max(x,y)
#define smin(x,y) x=min(x,y)
#define fmax(x,y,z) max(x,max(z,y))
#define fmin(x,y,z) min(x,min(z,y))
#define res(i,x,y) for(int i=x;i<=y;i++)
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define resl(i,x,y) for(ll i=x;i<=y;i++)
#define rezl(i,x,y) for(ll i=x;i>=y;i--)
#define INF 2100000000
#define MOD 1000000007
#define ll long long
#define N 200010
#define P 65536
#ifdef win32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
template <class T>
inline void readin(T &resez){
    static char ch;
    while((ch=getchar())<'0'||ch>'9');
        resez=ch-;
    while((ch=getchar())>='0'&&ch<='9')
        resez=resez*+ch-;
}
const ll M = +;
ll n,num[],s[M],a,C[M],B[M],cnt[];
ll power(ll a,ll b){
    ll ans=;
    while(b){
        if(b%==){
            ans=ans*a;
        }
        a=a*a;
        b/=;
    }
    return ans;
}
int main(){
    freopen("beleive.in","r",stdin);
    freopen("believe.out","w",stdout);
    readin(n);
    resl(i,,n){
        readin(a);
        resl(j,,){
            if((<<j)&a) num[j]++; 
            else cnt[j]++;
        }
        s[i]=a;
    }
    resl(i,,n){
        resl(j,,){
            if((<<j)&s[i]){
                B[i]+=power(,j)*(num[j]);
            }
        }
        cout<<B[i]<<' ';
    } 
    printf("\n");
    resl(i,,n){
        resl(j,,){
            if((<<j)&s[i]) {
                C[i]+=power(,j)*(num[j]+cnt[j]);
            }
            else{
                C[i]+=power(,j)*(num[j]);
            }
        }
        cout<<C[i]<<' ';
    }
    return ;
}

标答

這次标答的卻比所有人都優……

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

using namespace std ;

int n ;

const int MAXN =  ; 

typedef long long LL ; 

int cnt[MAXN], a[MAXN] ;

LL b[MAXN], c[MAXN]; 

int main() {
        freopen("beleive.in", "r", stdin) ;
        freopen("believe.out", "w", stdout) ; 
        scanf("%d", &n) ; 
        for (int i = ; i <= n; i ++) scanf("%d", &a[i]) ; 
        for (int i = ; i <= n; i ++) { 
                for (int j = ; j < ; j ++) {
                        if ((a[i] >> j) & ) cnt[j] ++ ; 
                }
        }
        for (int i = ; i <= n; i ++) {
                for (int j = ; j < ; j ++) { 
                        if ((a[i] >> j) & ) {
                                b[i] += L * cnt[j] * ( << j) ; 
                                c[i] += L * n * ( << j) ; 
                        }
                        else {
                                c[i] += L * cnt[j] * ( << j) ; 
                        }
                }
        }
        for (int i = ; i <= n; i ++) {
                printf(LLD "%c", b[i], (i == n ?  : ' ')) ; 
        }       
        for (int i = ; i <= n; i ++) {
                printf(LLD "%c", c[i], (i == n ?  : ' ')) ; 
        }
}

第二題：心（heart.cpp/c/pas)

11月18日——離noip還有1天[遊戲王YGO]每日推薦!總結

背景描述：

不是一切深淵都是滅亡

不是一切滅亡都覆寫在弱者的頭上

——《這也是一切》舒婷

有N個透明的盒子，每個盒子裡面有兩個不同顔色的球，總共有M種顔色。

Alice和Bob又在玩遊戲，具體的， Alice會從N個盒子裡面選出若幹個， Bob再從Alice選出的盒子裡面選出一些（不能不選），如果在Bob選出的盒子中，每個顔色的球都總共出現了偶數次（0次也是偶數次），那麼Bob勝利，否則Alice勝利

在Alice和Bob都足夠聰明的情況下， Alice想知道自己在能夠獲勝的前提下，第一次最多可以選出幾個盒子

輸入格式：

第一行有兩個整數N和M，意義如題

接下來N行，第i+1行兩個整數表示第i+1個盒子裡面的兩個球分别是什麼顔色的

輸出格式：

一行一個整數表示Alice最多可以選多少個盒子

樣例輸入：

3 3

1 2

2 3

2 3

樣例輸出：

2

資料規模：對于30%的資料， N <= 10

對于50%的資料， N <= 20

對于100%的資料， N <= 100000， M <= 2N

思考與題解

第二題：

将每一種顔色的球看成點，那麼一個盒子就是一條連接配接兩個點的邊。

選出的盒子如果構成了環，那麼Bob勝，否則Alice勝

也就是說我們現在要選出盡量多的邊，使得不存在環，直接并查集即可

并查集在此處

code

小編是通過建圖來解決的………………很慢…………

#include<set>
#include<list>
#include<deque>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
#include<map>
#define Li(x) x<<1
#define Ri(x) x<<1|1
#define clr(x) memset((x),0,sizeof(x))
#define cld(x) memset((x),127/2,sizeof(x))
#define smin(x,y) x=min(x,y)
#define smax(x,y) x=max(x,y)
#define smin(x,y) x=min(x,y)
#define fmax(x,y,z) max(x,max(z,y))
#define fmin(x,y,z) min(x,min(z,y))
#define res(i,x,y) for(int i=x;i<=y;i++)
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define INF 2100000000
#define MOD 1000000007
#define ll long long
#define N 200010
#define P 65536
#ifdef win32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
const int M = +;
int n,m,a,b,be[M],tot,num[M],ans;
template <class T>
inline void readin(T &resez){
    static char ch;
    while((ch=getchar())<'0'||ch>'9');
        resez=ch-;
    while((ch=getchar())>='0'&&ch<='9')
        resez=resez*+ch-;
}
struct Edge{
    int from,to;
    int belong;
}edge[M];
vector<int> g[M];
void dfs(int s){
    for (int i=;i<g[s].size();i++){
        int v=g[s][i];
        if(!be[v]){
            be[v]=be[s];
            dfs(v);
        }
    }
}
int main(){
    freopen("heart.in","r",stdin);
    freopen("haert.out","w",stdout);
    cin>>n>>m;
    res(i,,n){
        readin(a);readin(b);
        g[a].push_back(b);g[b].push_back(a);
        edge[i].to=a;edge[i].from=b;
    }
    res(i,,m){
        if(!be[i])be[i]=++tot;
        dfs(i);
    }
    res(i,,m)num[be[i]]++;
    res(i,,tot)ans+=num[i]-;
    cout<<ans;
    return ;
}

反正能AC

李ys的神奇代碼

但是标答或者說是更快的方法是李ys大神所用的并查集（Kruskal）就可以達到最快！！！

#include<iostream>
#include<cstdio>
#include<ctime>
#include<algorithm>
using namespace std;
const int MAX=*;
int fa[MAX],ans,n,m;
int findfa(int k)
{
    if (fa[k]==k) return k;
    return fa[k]=findfa(fa[k]);
}
inline int read()
{
    char x=(char)getchar();
    int re=;
    while (x<='9'&&x>='0')
    {
        re=re*+x-;
        x=getchar();
    }
    return re;
}
int main()
{
    freopen("heart.in","r",stdin);
    freopen("haert.out","w",stdout);
    n=read();m=read();
    for (int i=;i<=m;i++) fa[i]=i;
    for (int i=;i<=n;i++)
    {
        int x=read(),y=read();
        int f1=findfa(x);
        int f2=findfa(y);
        if (f1!=f2)
        {
            fa[f1]=f2;
            ans++;
        }
    }
    printf("%d",ans);
    return ;
}

第三題：題(problem.cpp/c/pas)

11月18日——離noip還有1天[遊戲王YGO]每日推薦!總結

背景描述：

黑夜給了我黑色的眼睛

我卻用它尋找光明

——《一代人》顧城

已知一個N個元素的非負整數序列A，

定義Bi = (Ai and A1) + (Ai and A2) + (Ai and A3)+ …… + (Ai and An)

定義Ci = (Ai or A1) + (Ai or A2) + … + (Ai or An)

給出B和C序列，構造一個滿足條件的A序列，如果沒有，輸出-1

輸入格式：

第一行一個整數N。

接下來一行N個整數表示B序列

接下來一行N個整數表示C序列

輸出格式：

如果有解，輸出一行N個整數表示你構造的A序列， SPJ很脆弱，是以你構造的序列每個整數必須在[0,8191]這個區間内，我們保證如果有解，那麼一定存在一個解滿足每個元素均在[0,8191]内

否則輸出-1

樣例輸入：

4

6 8 4 4

16 22 10 10

樣例輸出：

3 5 1 1

資料規模：

對于30%的資料， N = 2

對于70%的資料， N <= 200

對于100%的資料， N <= 100000， Bi , Ci<= 1000000000

題解

第三題：

第三題是第一題倒過來。

注意到對于任意兩個非負整數A， B。 A and B + A or B = A + B

于是Bi+Ci = A1 + A2 + ….. + An + Ai * n

我們可以把所有數求和，得到Ai的和，記為sum，再對每個數用Bi+Ci-sum / n 可以得到Ai

最後跑一遍第一題判定一下是否合法即可

值域在0到8191隻是為了随機資料随出來B和C都在1e9以内，沒有實際意義

聽小編一言，上訴都是渣渣！！！！！

看小編的代碼！！！！！

code（垃圾标程）

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;

int n ;

const int MAXN =  ;

typedef long long LL ;

int B[MAXN], C[MAXN], a[MAXN]; 

LL b[MAXN], c[MAXN] ;

struct Node {
        int b, c, id ;
        bool operator < (const Node ano) const {
                return b + c < ano.b + ano.c ;
        }
} opt[MAXN] ; 

int cnt[MAXN] ;
bool check(int x) { 
        int now = x ; 
        for (int i = ; i <= n; i ++) { 
                a[opt[i].id] = now ; 
                now += ((opt[i + ].b + opt[i + ].c - opt[i].b - opt[i].c) / n) ; 
        }
        memset(cnt, , sizeof cnt) ; 
        memset(b, , sizeof b) ;
        memset(c, , sizeof c) ;
        for (int i = ; i <= n; i ++) { 
                for (int j = ; j < ; j ++) {
                        if ((a[i] >> j) & ) cnt[j] ++ ; 
                }
        }
        for (int i = ; i <= n; i ++) {
                for (int j = ; j < ; j ++) { 
                        if ((a[i] >> j) & ) {
                                b[i] += L * cnt[j] * ( << j) ; 
                                c[i] += L * n * ( << j) ; 
                        }
                        else {
                                c[i] += L * cnt[j] * ( << j) ; 
                        }
                }
        }
        return b[] + c[] >= B[] + C[] ; 
}

bool check2(int x) { 
        int now = x ; 
        for (int i = ; i <= n; i ++) { 
                a[opt[i].id] = now ; 
                now += ((opt[i + ].b + opt[i + ].c - opt[i].b - opt[i].c) / n) ; 
        }
        memset(cnt, , sizeof cnt) ; 
        memset(b, , sizeof b) ;
        memset(c, , sizeof c) ; 
        for (int i = ; i <= n; i ++) { 
                for (int j = ; j < ; j ++) {
                        if ((a[i] >> j) & ) cnt[j] ++ ; 
                }
        }
        for (int i = ; i <= n; i ++) {
                for (int j = ; j < ; j ++) { 
                        if ((a[i] >> j) & ) {
                                b[i] += L * cnt[j] * ( << j) ; 
                                c[i] += L * n * ( << j) ; 
                        }
                        else {
                                c[i] += L * cnt[j] * ( << j) ; 
                        }
                }
        }
        for (int i = ; i <= n; i ++) { 
                if ((b[i] != B[i]) || (c[i] != C[i])) return  ; 
        }
        return ;  
}



int main() { 
        freopen("problem.in", "r", stdin) ; 
        freopen("problem.out", "w", stdout) ; 
        scanf("%d", &n) ; 
        for (int i = ; i <= n; i ++) scanf("%d", &opt[i].b), B[i] = opt[i].b, opt[i].id = i  ;
        for (int i = ; i <= n; i ++) scanf("%d", &opt[i].c), C[i] = opt[i].c ; 
        sort(opt + , opt + n + ) ;
        for (int i = ; i <= n; i ++) {
                if ((opt[i].b + opt[i].c - opt[i - ].b - opt[i - ].c) % n != ) {
                        puts("-1") ;
                        return  ; 
                }
        }
        int l = , r =  ; 
        while (l < r) {
                int mid = (l + r) >> ; 
                if (check(mid) ) r = mid ;
                else l = mid +  ; 
        }
        if (check2(l)) {
                for (int i = ; i <= n; i ++) printf("%d%c", a[i], (i == n ?  : ' ')) ;
        }
        else puts("-1") ;
}

xc大大的O（n）解法

A+B=A&B+A|B

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define name "problem"
#define maxn 100009
typedef long long ll;
using namespace std;
ll b[maxn],c[maxn],a[maxn];
void get(ll &y) {
    y=;
    char x=getchar();
    while('0'>x||x>'9')
        x=getchar();
    while('0'<=x&&x<='9')   {
        y=y*+x-'0';
        x=getchar();
    }
}
int main()  {
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    ll n;
    get(n);
    ll sum=;
    for(int i=;i<=n;i++)   {
        get(b[i]);
        sum+=b[i];
    }
    for(int i=;i<=n;i++)   {
        get(c[i]);
        sum+=c[i];
    }
    if(sum%(*n)==)
        sum/=*n;
    else {
        cout<<-<<endl;
        return ;
    }
    for(int i=;i<=n;i++)   {
        if((b[i]+c[i]-sum)%n==)
            a[i]=(b[i]+c[i]-sum)/n;
        else    {
            cout<<-<<endl;
            return ;
        }
    }
    for(int i=;i<=n;i++)   {
        cout<<a[i]<<(i==n ? "\n" : " ");
    }
}

總結

今天也無力回天了……

面對現實吧，小編自己隻是個渣渣……………………

然後預祝所有的OIer考試順利！！！

（自己更加順利！！！！！）

（沒有高精度！！！）

（今天忘發圖！！！）

11月18日——離noip還有1天[遊戲王YGO]每日推薦!總結

每日推薦!

第一題：信(believe.cpp/c/pas)

思考與題解

code

标答

第二題：心（heart.cpp/c/pas)

思考與題解

code

李ys的神奇代碼

第三題：題(problem.cpp/c/pas)

題解

code（垃圾标程）

xc大大的O（n）解法

總結

繼續閱讀

【基礎】高精度乘法

《Java從小白到大牛精簡版》之第6章運算符（下）

HDU 4059解題報告 The Boss on Mars

在1001個數中，隻有一個數是重複的，其他的都是一個。請找出重複的數。

hdu 1695（歐拉函數+容斥原理）

hdu1695 (容斥原理+歐拉函數）

UVA 10718 Bit Mask

UVA 10954 Add All

51nod 1486 大大走格子[容斥原理]

51nod 1486 大大走格子（dp，容斥）

codeforces 1475 C Ball in Berland

NOIP2016集訓總結

容斥原理-shuoj—小明系列之高中時光

[LeetCode]Single Number II

hdu 5023 A Corrupt Mayor's Performance Art（線段樹+位運算）

黑馬程式員----------java基礎知識(2)