2016 ICPC 大连站解题报告

J. Find Small A

一眼题没看清以为移4位WA了一次

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while (scanf("%d",&n)!=EOF) {
        int ans=0;
        for (int i=1;i<=n;i++) {
            int x;
            scanf("%d",&x);
            while (x) {
                ans+=((x&255)=='a');
                x>>=8;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

H. To begin or not to begin

简单计算或者由生活常识：每次抽中红球的概率都是相等的，所以只需要判断先后手抽的次数，也就是判断奇偶性。这里题目没说k是什么，但是看样例应该差不多反正先随便交一发【据说当时pc^2上还给了错误的解释。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while (scanf("%d",&n)!=EOF) {
        printf("%d\n",(n+1)&1);
    }
    return 0;
}

I. Convex

正弦面积公式，注意角度弧度转换

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

const double PI=acos(-1.0);

int main()
{
    int n,r;
    while (scanf("%d%d",&n,&r)!=EOF) {
        long double ans=0;
        for (int i=1;i<=n;i++) {
            int a;
            scanf("%d",&a);
            ans+=sin(a/180.0*PI)*r*r;
        }
        double outter=ans/2.0;
        printf("%.3f\n",outter);
    }
    return 0;
}

D. A Simple Math Problem

比较 $simple$ ，看到 $LCM$ 想到 $GCD$ 。
原题即为$$(p,q)=1$$$$pg+qg=a$$$$pqg=b$$
可以发现必须有 $g=(a,b)$ 。最后输出 $pg,qg$ 即可。
交上去发现只有我 OLE，结果是忘记打 !=EOF 了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;

ll gcd(ll a,ll b)
{
    if (!b) return a;
    return gcd(b,a%b);
}

int main()
{
    ll a,b;
    while (scanf("%lld%lld",&a,&b)!=EOF) {
        ll g=gcd(a,b);
        a/=g;b/=g;
        ll tmp=a*a-4*b;
        if (tmp<0) {
            puts("No Solution");
            continue;
        }
        ll x=sqrt(tmp);
        if (x*x!=tmp) {
            puts("No Solution");
            continue;
        }
        if ((a+x)&1||a<=x) {
            puts("No Solution");
            continue;
        }
        ll p=(a+x)/2*g;
        ll q=(a-x)/2*g;
        if (p>q) swap(p,q);
        printf("%lld %lld\n",p,q);
    }
    return 0;
}

A. Wrestling Match

其实我先写的 A 。。。但是写到一半感觉有点写不下去又看到 D 比较 simple 就去搞 D 了。。。简单的说就是从所给的已知好坏的点开始搜索。。。这些点搜索完了再搜索剩下的点。。。如果某个点不是已知点，并且不与其他点连边，那么它无法被分类。。。听说很多人卡题意卡了半天。。。我觉得我也说不出来准确的题意= =。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int N=1010;
vector<int> eg[N];
vector<int> good,bad;
int col[N];
int n,m;

bool bfs(int x,int c)
{
    col[x]=c;
    queue<int> Q;
    Q.push(x);
    while (!Q.empty()) {
        int u=Q.front();
        Q.pop();
        for (int i=0;i<eg[u].size();i++) {
            int &v=eg[u][i];
            if (col[v]==-1) {
                col[v]=col[u]^1;
                Q.push(v);
            } else if (col[v]==col[u]) {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF) {
        for (int i=1;i<=n;i++) {
            eg[i].clear();
        }
        good.clear();
        bad.clear();
        int x,y;
        scanf("%d%d",&x,&y);
        for (int i=1;i<=m;i++) {
            int u,v;
            scanf("%d%d",&u,&v);
            eg[u].push_back(v);
            eg[v].push_back(u);
        }
        memset(col,0xff,sizeof(col));
        
        for (int i=0;i<x;i++) {
            int k;
            scanf("%d",&k);
            col[k]=1;
            good.push_back(k);
        }
        for (int i=0;i<y;i++) {
            int k;
            scanf("%d",&k);
            col[k]=0;
            bad.push_back(k);
        }
        
        int f=0;
        for (int i=0;i<x;i++) {
            if (!bfs(good[i],1)) {
                f=1;
                break;
            }
        }
        if (f) {
            puts("NO");
            continue;
        }
        
        for (int i=0;i<y;i++) {
            if (!bfs(bad[i],0)) {
                f=1;
                break;
            }
        }
        if (f) {
            puts("NO");
            continue;
        }
        
        for (int i=1;i<=n;i++) {
            if (col[i]==-1) {
                if (eg[i].size()==0) {
                    f=1;
                    break;
                }
                if (!bfs(i,0)) {
                    f=1;
                    break;
                }
            }
        }
        if (f) puts("NO");
        else puts("YES");
    }
    return 0;
}

然后不知道搞啥。。。咸鱼了挺久。。。

E. Aninteresting game

终于把E读懂感觉这不是sb题吗。。。题解重点讲的询问1一遍写对，询问2倒是想错了好多次。。。 OTZ
询问1 其实就是求 $\sum_{i=l}^{r} lowbit(i)$ 只要枚举 $lowbit$ 的值就行了。。。不过每次要把上一次重复的去掉一些。。。
询问2 我想的是可以把除了最后一段 0 的其它 0 的位置填成 1（见 Method One） 。。。不过这个操作建议看题解，写得更清晰，而且只用到了 $lowbit$ （见 Method Two）。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main()
{
    ll n,q;
    while (scanf("%lld%lld",&n,&q)!=EOF) {
        while (q--) {
            int op;
            scanf("%d",&op);
            if (op==1) {
                ll l,r;
                scanf("%lld%lld",&l,&r);
                ll ans=0,weigh=1;
                while (weigh<=r) {
                    ll tmp=r/weigh-(l-1)/weigh;
                    if (tmp==0) break;
                    ans-=tmp*(weigh>>1);
                    ans+=tmp*weigh;
//                    printf("TMP: %lld\nANS: %lld\n",tmp,ans);
                    weigh<<=1;
                }
                printf("%lld\n",ans);
            } else {
                ll x,ans=0;
                scanf("%lld",&x);
                
                /***Method One***/
                int k=0;
                while (((x>>k)&1)==0) k++;
                for (;;k++) {
                    if (((x>>k)&1)==0) {
                        if ((((x>>k)^1)<<k)<=n) ans++;
                        else break;
                    }
                }
                printf("%lld\n",ans+1);
                /***Method One***/
                
                /***Method Two***/
//                while (x<=n) {
//                    ans++;
//                    x+=x&(-x);
//                }
//                printf("%lld\n",ans);
                /***Method Two***/
            }
        }
    }
    return 0;
}

F. Detachment

想得不怎么清楚。。。天猫教我的。。。
肯定从小的开始乘，这个还是比较显然的，所以刚开始先生成 $2\times 3\times…\times k$ ，多出来一个小于 $k+1$ 的数，这时可以从后往前把一段数 +1 ，因为小的数贡献大，而且小的数如果 +1 就会和后面相同。不过这里又会有一个问题，就是剩下的数是 $k$ ，而前面只有 $k-1$ 个数。。。那这时就要取一个数和这个 $k$ 加起来变成一个新的数，那么很显然要取 $2$ （为什么？）（Hint：结果的倍数）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MOD=1e9+7;
const int MAX=1e5;
ll fac[MAX];

ll fpow(ll x,ll n)
{
    ll res=1;
    while (n) {
        if (n&1) {
            res=res*x%MOD;
        }
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}

int main()
{
    fac[0]=1;
    for (int i=1;i<MAX;i++) {
        fac[i]=fac[i-1]*i%MOD;
    }
    int T;
    scanf("%d",&T);
    while (T--) {
        ll n,ans;
        scanf("%lld",&n);
        if (n==1) {
            puts("1");
            continue;
        }
        ll x=sqrt((n+1)*2);
        if (x*(x+1)/2>n+1) x--;
        ll rem=n+1-x*(x+1)/2;
        if (rem==x) {
            ans=fac[x]*fpow(2,MOD-2)%MOD*(x+2)%MOD;
        } else {
            ans=fac[x-rem]*fac[x+1]%MOD*fpow(fac[x-rem+1],MOD-2)%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}