太晚了…并没有参加比赛…这几天做了一下…
从雪下做到雪融(菜爆了)…

懵逼的 题目

传送至 CrossFire

扯淡的 题解

A

Emmmmmm…水…

B

并没有看过几集Conan…
考虑只有一些相等的数:

  • 偶数先手输
  • 奇数先手赢

(因为只会去掉严格小于选择的数的数, 所以和这个数相等的数并不会去掉, 所以一次只能取走一个)

然后考虑最大的数:

  • 如果最大数有奇数个, 一定先手赢
  • 如果最大的数有偶数个, 一定先手输

(第一次就把不是最大的数全部去掉了, 只剩下奇数或偶数个相等的数, 而一次仍然只能去掉一个数)

所以考虑Conan的最优策略: 如果最大数是偶数个, Conan一定不会去取最大数(因为先手就输了), 所以Conan就会去看倒数第二大的数, 而Agasa也不会去取最大数(不傻), 如果倒数第二大的数的个数是偶数, 那么取完倒数第二大的数还是Conan先手, GG, 如果是奇数, 取完倒数第二大的数后先后手翻转, Conan就赢了…所以就有了算法:

  1. 排序, 让相等的数在一起
  2. 从大到小扫描, 如果找到一些相等的数个数是奇数, 返回Canon赢, 如果一直到了最后还是相等的数都是偶数, 返回Agasa赢

水…30min- 1A

C

思路很显然, 因为logn的范围比较小, 我们就可以求出 [1 ~ log(n)]中所有数变成1的次数, 找所有次数为k - 1的数(cans[]), 这些数就是一个Ans的二进制位中1的个数(不要忘了变成cans[]还需要一步), 然后用数位DP的思想(舒老师原话%%%)枚举给定n的每一位, 如果这一位是1, 设答案的这一位为0(保证了比n要小), 然后加上剩余1的个数在剩下的位数中组合的方案数, 然后把剩余1的个数–(表示这一位也放上1, 保证置零前的二进制位和n的一样), 最后加上和n相等的方案数

有很多细节要注意…好多Dalao都被Hack点艹翻了…比如考虑相等的情况, 和k == 0的情况和n == 0的情况…
还有…

10000000000000000000000000000
1

这种恶心的Hack点…答案要减一…因为1在最后一位的时候其实是不合法的…

D

反而相对来说简单一点…显然如果一个区间要满足[可以改动一个数就以x为GCD]必须让[最多一个数不能整除GCD]我们发现[区间是否可以整除一个数]是可以区间合并的(取两个子区间的GCD的GCD即可), 所以我们就可以用线段树了…

查找的话就是如果这个区间的GCD能整除x, 就返回, 否则看哪个子区间不能整除x, 查询这个子区间, 直到找到不能整取的单个数, ok++, 如果ok > 1就输出"NO"

总之…

AB倒都是秒了…CD一个从七点调到十二点, 从机房调到了家里, 一个也是调了两节课发现某些实现有问题
题目并不难, 但是代码能力还是菜的一批, 主要大概是一直闷头调试的问题, 之后一时调到焦头烂额就应该出去洗把脸, 理一理思路(C就是回家的路上想到哪里出了问题的), 还有…不能再一不小心看见标签了…Emmmmm
又: 是不是该准备期末考试了…

沙茶的 代码

A

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN (1000 + 5)
using namespace std;
int n, a[MAXN];
bool cmp(int, int);
void solve();
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    solve();
    return 0;
}
bool cmp(int x, int y)
{
    return x > y;
}
void solve()
{
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        int x = (int)sqrt(a[i]);
        if (x * x != a[i])
        {
            printf("%d\n", a[i]);
            return ;
        }
    }
}

B

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int n;
int a[MAXN];
bool Conanwin;
void solve();
bool cmp(int, int);
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    solve();
    if (Conanwin)
        puts("Conan");
    else
        puts("Agasa");
    return 0;
}
void solve()
{
    sort(a + 1, a + n + 1, cmp);
    int last = a[1], cnt = 0;
    for (int i = 1; i <= n;)
    {
        while (a[i] == last)
        {
            ++i;
            ++cnt;
        }
        last = a[i];
        if (cnt & 1)
        {
            Conanwin = true;
            return ;
        }
    }
    Conanwin = false;
    return ;
}
bool cmp(int x, int y)
{
    return x > y;
}

C

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#define MAXB (1010 + 5)
#define MAXK (1010 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define REFUN (1000000000 + 7)
#define LL long long
using namespace std;
int n, k, suma;
bool a[MAXB];
LL c[MAXB][MAXK], f[MAXB], ans; // f[i]: i需要多少步归一
void initf();
void initc();
void solve();
inline int bit1(int);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string srs;
    cin >> srs >> k;
    if (!k)
    {
        puts("1");
        return 0;
    }
    if (srs == "1")
    {
        puts("0");
        return 0;
    }
    n = srs.length();
    for (int i = 0; i < n; i++)
    {
        a[n - i] = (srs[i] == '1');
        if (a[n - i])
            ++suma;
    }
    initc();
    initf();
    solve();
    /*if (ans == 157)
    {
        cout << 158;
        return 0;
    }*/
    cout << ans % REFUN;
    return 0;
}
inline int bit1(int x)
{
    int re = 0;
    while (x)
    {
        re = ((x & 1) ? (re + 1) : (re));
        x >>= 1;
    }
    return re;
}
void initc()
{
    memset(c, 0, sizeof(c));
    c[0][0] = 1;
    c[0][1] = c[1][1] = 1;
    for (int i = 2; i < MAXB; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (!j)
                c[j][i] = c[j][i - 1];
            else
                c[j][i] = (c[j - 1][i - 1] + c[j][i - 1]) % REFUN;
//            cout << j << " " << i << " " << c[14][0] << endl;
        }
    }
}
/*
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
*/
void initf()
{
    memset(f, 0x7f, sizeof(f));
    f[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (bit1(j) == i)
                f[j] = min(f[j], (f[i] + 1) % REFUN);
        }
    }
}
void solve()
{
    vector<int> cans;
    for (int i = 1; i <= n; i++)
    {
        if (f[i] == k - 1)
        {
            /*if (i == suma)
                ++ans;*/
            cans.push_back(i);
        }
    }
    int cnn = cans.size();
    /*
    for (int i = 0; i < cnn; i++)
    {
        ans += c[cans[i]][n - 1];
        ans %= REFUN;
    }
    */
    int cnt1 = 0; //代表之前有几个1是相同的(即已经放过几个1了)
    for (int i = n; i >= 1; i--)
    {
        while (!a[i] && i > 1)
        {
            --i;
        }
        if (!a[i])
            break;
        for (int j = 0; j < cnn; j++)
        {
            if (cans[j] < cnt1)
                continue;
            ans += c[cans[j] - cnt1][i - 1];
            if (cans[j] == 1 && i == n)
                --ans;
            ans %= REFUN;
        }
        ++cnt1;
    }
    for (int i = 0; i < cnn; i++)
    {
        if (cans[i] == suma)
        {
            ++ans;
        }
    }
}

/*
111111011
2

确定了在n位中有x位是1
看看怎么做到比这个小
首先C(x, n - 1)肯定可以
然后从高位逐位相等看看比这个小的有多少
*/

D

XP学长: 我这道题想到思路以后就去打炉石了%%%

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (500000 + 5)
#define INF (0x7ffffff)
#define LL long long
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
using namespace std;
struct node
{
    int le, ri, zh;
}b[MAXN << 3];

int n, a[MAXN];
int ok;
void js(int, int, int);
void xg(int, int, int);
void cx(int, int, int, int);
int gcd(int, int);
inline void pushup(int);
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    js(1, 1, n);
    int q, srx, sry, srz, sre;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d%d", &sre, &srx, &sry);
        if (sre & 1)
        {
            scanf("%d", &srz);
            ok = 0;
            cx(1, srx, sry, srz);
            if (ok <= 1)
                puts("YES");
            else
                puts("NO");
        }
        else
            xg(1, srx, sry);
    }
    return 0;
}
int gcd(int a, int b)
{ return ((b == 0) ? (a) : (gcd(b, a % b))); }
inline void pushup(int dq)
{ b[dq].zh = gcd(b[LS(dq)].zh, b[RS(dq)].zh); }
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    if (le == ri)
    {
        b[dq].zh = a[le];
        return ;
    }
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
    pushup(dq);
}
void xg(int dq, int wz, int zh)
{
    if (b[dq].le == b[dq].ri && b[dq].le == wz)
    {
        b[dq].zh = zh;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (wz <= mi)
        xg(LS(dq), wz, zh);
    else 
        xg(RS(dq), wz, zh);
    pushup(dq);
}
void cx(int dq, int le, int ri, int zh)
{
    if (!(b[dq].zh % zh))
        return ;
    if (b[dq].le == b[dq].ri && le == ri)
    {
        if (b[dq].zh % zh)
            ++ok;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (ri <= mi)
        cx(LS(dq), le, ri, zh);
    else if (le > mi)
        cx(RS(dq), le, ri, zh);
    else
    {
        if (b[LS(dq)].zh % zh)
            cx(LS(dq), le, mi, zh);
        if (ok > 1)
            return ;
        if (b[RS(dq)].zh % zh)
            cx(RS(dq), mi + 1, ri, zh);
    }
}

By 期末药丸的 Cansult

话说我怎么攻变受了啊