Starry

发表于 更新于 分类于 本文字数： 452 阅读时长 ≈ 2 分钟

差亿点过三题

A题，考虑将相同的字母压缩，要也即要压缩后的字符数为奇数，考虑修改则需要修改开头或者结尾。

这时考虑到修改一位便可，于是只需

1
s[0]=s.back();

B题,先求出k在二进制下最高位1的位置，然后按等比数列求和求出如果就模拟，否则就除k算。

不开long long见祖宗。菜鸡

C题,考虑到，先预处理出十的幂与各幂次之间允许的次数

A: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
LL t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    f(sb,1,t){
        string s;
        cin>>s;
        vector<pii> v;
        char last=s[0];
        int cnt=0;
        for(auto it:s){
            if(it!=last){
                v.pb(mp(last,cnt));
                last=it;
                cnt=1;
            }
            else cnt+=1;
        }
        v.pb(mp(last,cnt));
        if(v.size()&1)
        cout<<s<<"\n";
        else {
            if(s[0]=='a') s[0]='b';
            else s[0]='a';
            cout<<s<<"\n";
        }
    }
    return 0;
}

B:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
LL quikpower(int b)
{
    LL ans = 1, base = 2;
    while (b > 0)
    {
        if (b & 1)
        {
            ans *= base;
        }
        base *= base;
        b >>= 1;
    }
    return ans;
}
 
LL t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    f(ab, 1, t)
    {
        LL n, k, bas = 1, cnt = 0;
        cin >> n >> k;
        n -= 1;
        LL sb = k;
        while (sb > 0)
        {
            sb>>=1;
            cnt += 1;
        }
        LL ma=quikpower(cnt)-1;
        if (n <ma)
        {
            cnt=0;
            while (n > 0)
            {
                cnt += 1;
                n -= bas;
                bas *= 2;
            }
        }
        else if(n>ma)
        {
            n-=ma;
            cnt+=(n/k+(n%k?1:0));
        }
        cout << cnt << "\n";
    }
    return 0;
}

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
LL t,n,k;
LL a[11]={1};
LL b[11]={0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    f(i,1,9){
        a[i]=a[i-1]*10;
        b[i]=b[i-1]*10+9;
    }
    cin>>t;
    f(sb,1,t){
        cin>>n>>k;
        k+=1;
        vi v;
        LL ans=0;
        f(i,1,n){
            LL temp;
            cin>>temp;
            v.pb(temp);
        }
        auto it=v.begin();
        it++;
        while(it!=v.end()&&k>0){
            LL mid=min(k,b[(*it)-(*(it-1))]);
            ans+=mid*a[(*(it-1))];
            //cout<<b[(*it)-(*(it-1))]<<"::::"<<(*it)-(*(it-1))<<"hw\n";
            k-=mid;
            it++;
        }
        if(k>0){
            ans+=k*a[(*(it-1))];
        }
        cout<<ans<<"\n";
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 15 阅读时长 ≈ 1 分钟

一直用的都是“错误”写法。

组合数写法

发表于 更新于 分类于 本文字数： 171 阅读时长 ≈ 1 分钟

感受到了div.3的友好度

A题先求出三数最大值，然后判断有多少个数等于，如果个数大于等于，则对于第个数输出为，否则的话最大值输出，其他数输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
LL t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){
        LL a,b,c;
        cin>>a>>b>>c;
        LL a1=max(a,b),a2=max(b,c);
        LL temp=max(a1,a2);
        LL res=(a==temp)+(b==temp)+(c==temp);
        if(res>1)res=1;
        else res=0;
        if(a==temp)
        cout<<temp+res-a<<" ";
        else cout<<temp+1-a<<" ";
        if(b==temp)
        cout<<temp+res-b<<" ";
        else cout<<temp+1-b<<" ";
        if(c==temp)
        cout<<temp+res-c<<"\n";
        else cout<<temp+1-c<<"\n";
    }
    return 0;
}

B题

发表于 更新于 分类于 本文字数： 737 阅读时长 ≈ 3 分钟

数据太弱，错误判断都能过。。

1
2
if(cnt[0]+cnt[1]==0)
        break;
A:

先考虑是一道数学题，对于某一位上出现的次数，我们可由数学知识推出为，而求出该组合数与Codeforces Round #745 (Div. 2)的D题一致。

注意oj数据后带无效空格？回车，单纯getchar判断会报WA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
LL n, k, c[N][N], mark = 2;
LL quikpower(int b)
{
    LL ans = 1, base = 2;
    while (b > 0)
    {
        if (b & 1)
        {
            ans *= base;
            ans %= p;
        }
        base *= base;
        base %= p;
        b >>= 1;
    }
    if (ans == 0)
        return p - 1;
    else
        return ans - 1;
}

int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    c[0][0] = c[1][1] = c[1][0] = 1;
    while (scanf("%lld%lld", &n, &k) == 2)
    {
        f(i, mark, n)
        {
            c[i][i] = c[i][0] = 1;
            for (int j = 1; j < i; j++)
            {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;
            }
        }
        mark = mark < n ? n : mark;
        cout << quikpower(n) * c[n - 1][k - 1] % p << '\n';
    }
    return 0;
}

B:

考虑异或的性质，我们先求出两个数组每一位上和的个数
求出每一位上的异或值再乘以基数，即：
最后累加即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const LL N = 1e5 + 86,p=1e9+7;
LL n, m, a[N], b[N], cnt[2],ans,base=1;
int main()
{
    //IN;OUT;
    n = io.xint();
    m = io.xint();
    f(i, 1, n) a[i] = io.xint();
    f(i, 1, m) b[i] = io.xint();
    f(k, 1, 31)
    {
        cnt[0]=cnt[1]=0;
        f(i, 1, n)
        {
            if (a[i] & 1)
            cnt[0]+=1;
            a[i]>>=1;
        }
        f(i,1,m){
            if(b[i]&1)
            cnt[1]+=1;
            b[i]>>=1;
        }
      /*if(cnt[0]+cnt[1]==0)
        break;*/
        ans+=base*((cnt[0]*(m-cnt[1])+cnt[1]*(n-cnt[0]))%p)%p;
        ans%=p;
        base<<=1;
        base%=p;
    }
    io.wll(ans);
    return 0;
}

C:

列几个情况贪心即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LL n,x,y,res=0,lx,ly;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>lx>>ly;
    f(sb,2,n){
        cin>>x>>y;
        res+=abs(x-lx)<abs(y-ly)?abs(y-ly):abs(x-lx);
        lx=x,ly=y;
    }
    cout<<res;
    return 0;
}

D:

先预处理出结果用bitset储存，然后直接判断，辣鸡1也是YES

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bitset<100009> vis;

int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    vis.reset();
    vis[1]=1;
    for (int k = 2; k <= 100000; k++)
    {
        LL temp =k;
        while(temp*k<=100000){
            temp*=k;
            vis[temp]=1;
        }
    }
    while (1)
    {
        LL n;
        cin >> n;
        if(n==0)break;
        if (vis[n])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

E不会，老是WA

F:

二维前缀和模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const LL N = 1e3 + 86;
LL n, m, s[N][N],temp;

inline LL getsum(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] + s[x1 - 1][y1 - 1] - s[x1 - 1][y2] - s[x2][y1 - 1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    f(k, 1, n)
    {
        f(j, 1, m)
        {
            cin>>temp;
            s[k][j] = s[k - 1][j] + s[k][j - 1] - s[k - 1][j - 1] + temp;
        }
    }
    f(i,1,n){
        f(j,1,m){
            cout<<getsum(1,1,i,j)<<(j==m?"":" ");
        }
        cout<<(i==n?"":"\n");
    }
    return 0;
}

G:

按题意搞即可，可采用位操作优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LL cnt=0;
char c;

int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(~(c=getchar())){
        while(c>0){
            if(c&1)
            cnt+=1;
            c>>=1;
        }
    }
    cout<<(cnt&1);
    return 0;
}

发表于 更新于 分类于 本文字数： 871 阅读时长 ≈ 3 分钟

同样只过了A题

英文菜鸡，看样例才知道是不能连续使用同一weapon然后还**地分的情况

UPD:

B题和做的思路差亿点点，可惜自己多虑跑去干E
由题意得出在区间内的元素无法进行题中操作，所以只需对原数组进行排序，然后比对区间内与原数组位序是否相同

E题：

首先切入点是考虑每一位上的情况：对于第位到第位，如果在区间满足题设条件，那么比较强的要求是：在区间上第位的异或值为，按位与值为,而对于第位至最高位的异或值也为，那么显然要完成该要求就需要为偶数

而事实上如果遍历每一位的较强要求下的结果，就能覆盖到原题较弱要求下的解

然后上快读都被报TLE，最后map换成cc_hash_table才3166ms苟过测试点9

UPD: C如果所有节点异或和为，那么容易在任意节点间断开均可。否则的话k就必须大于。

而对于分割成三个部分以上的情况，可以合并成个部分，所以我们现在只需判断能否切成三部分。

A: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const LL N = 1e3 + 86;

LL t, n, h, a[N], dp[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    f(sb, 1, t)
    {
        cin >> n >> h;
        f(i, 1, n) cin >> a[i - 1];
        sort(a, a + n);
        LL max1, max2;
        max1 = a[n - 1];
        max2 = a[n - 2];
        LL res = h / (max1 + max2) * 2;
        h %= (max1 + max2);
        while (h > 0)
        {
            if (res & 1)
                h -= max2;
            else
                h -= max1;
            res += 1;
        }
        cout << res << '\n';
    }
    return 0;
}
B 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
onst LL N = 1e5 + 86;
LL t, n, x, a[N], b[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    f(sb, 1, t)
    {
        cin >> n >> x;
        bool vis = 1;
        f(i, 1, n)
        {
            cin >> a[i - 1];
            b[i - 1] = a[i - 1];
        }
        sort(a, a + n);
        for (int i = n - x; i <= x - 1; i++)
        {
            if (a[i] != b[i])
                vis = 0;
        }
        if (vis)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}
E 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

onst LL N = 1e6 + 86;
LL n, a[N], ans, pref[N];

int main()
{
    //IN;
    //OUT;
    n = io.xint();
    f(i, 1, n) a[i] = io.xint();
    for (int k = 20; k >= 0; k--)
    {
         __gnu_pbds::cc_hash_table<LL, std::vector<LL> > vis[2];
        vis[0][0].pb(0);
        f(i, 1, n) pref[i] = (a[i] >> k) ^ pref[i - 1], vis[i & 1][pref[i]].pb(i);
        LL l = 0;
        for (LL r = 1; r <= n; r++)
        {
            if ((a[r] >> k) & 1)
            {
                std::vector<LL> &v = vis[r & 1][pref[r]];
                std::vector<LL>::iterator it = std::lower_bound(v.begin(), v.end(), l);
                if(it != v.end())
                    ans = ans < r - *it ? r - *it : ans;
            }
            else l=r;
        }
    }
    io.wll(ans);
    return 0;
}
C: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
const int N = 1e5 + 86;
int t, n, k, a[N], xo[N], x, c, b, flag;
vector<int> v[N];

int dfs(int now, int fa)
{
    xo[now] = a[now];
    for (auto it : v[now])
    {
        if (it == fa)
            continue;
        xo[now] ^= dfs(it, now);
    }
    return xo[now];
}

void fi(int now, int fa)
{
    for (auto it : v[now])
    {
        if (it == fa)
            continue;
        fi(it, now);
        if (xo[it] == x && flag == 0)
        {
            flag = 1;
            v[now].erase(find(v[now].begin(), v[now].end(), it));
            return;
        }
    }
}

int main()
{
    //IN;
    //OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    t = io.xint();
    f(sb, 1, t)
    {
        x = 0;
        n = io.xint();
        k = io.xint();
        f(i, 1, n)
        {
            a[i] = io.xint();
            x ^= a[i];
            v[i].clear();
        }
        f(i, 1, n - 1)
        {
            c = io.xint();
            b = io.xint();
            v[c].pb(b);
            v[b].pb(c);
        }
        if (x == 0)
        {
            io.wstring("YES\n");
            continue;
        }
        else if (k == 2)
        {
            io.wstring("NO\n");
            continue;
        }
        flag = 0;
        dfs(1, 1);
        fi(1, 1);
        //io.wll(flag);
        if (flag == 1)
        {
            flag = 0;
            dfs(1, 1);
            fi(1, 1);
            if (flag == 1)
                io.wstring("YES\n");
            else
                io.wstring("NO\n");
            continue;
        }
        io.wstring("NO\n");
    }
    return 0;
}

0%