Diposting di | Edited on

传送门

E - Superhero Battle （数学）

思路

首先分为情况

如果在第一轮内就打死

或者如果一整轮的伤害大于等于0那一轮相当于白费

如果小于0那就说明肯定可以把怪物打死

所以我们就枚举在第K论之后的哪一回合打死即可

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+50;
typedef long long ll;

ll H,n;
ll d[maxn];
ll mx=2e18+50;
ll s[maxn];
int main(){

    std::ios::sync_with_stdio(false);
    cin>>H>>n;
    ll sum=0;
    for(ll i=1;i<=n;i++)cin>>d[i],sum+=d[i],s[i]=s[i-1]+d[i];

    for(ll i=1;i<=n;i++){
        if(-s[i]>=H)mx=min(mx,i);
    }
    if(sum<0){
        for(ll i=1;i<=n;i++){
            ll now=sum+s[i];
            now=-now;
            //cout<<"i="<<i<<" now="<<now<<endl;
            if(now>=H)mx=min(mx,i+n);
            else{
                ll ned=-sum;
                ll HH=H;
                HH-=now;
                ll time=HH/ned;
                if(HH%ned)time++;

                mx=min(mx,time*n+i+n);
            }
        }
    }
    if(mx==2e18+50)cout<<-1<<endl;
    else
        cout<<mx<<endl;
    return 0;
}
/*
1000000000000
4999999999996
*/

F2 - Same Sum Blocks (Hard) (贪心)

思路

首先枚举右端点 同时枚举左端点如果对于这一区间的权值保存的右端点比左端点还大那就加入他，同时更新答案

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+50;
typedef long long ll;

map<int,pair<int,int> >mp;

///区间和，次数，最后一次右边界
int sum[1550],a[1550];
vector<int>G;
struct node{
    int num;
    int R;
    vector<pair<int,int> >ve;
}my[1500*1500/2+50];
int id(int x){
    return lower_bound(G.begin(),G.end(),x)-G.begin();
}
int main(){

    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];

    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=i;j<=n;j++){
            sum+=a[j];
            G.push_back(sum);
        }
    }
    sort(G.begin(),G.end());
    G.erase(unique(G.begin(),G.end()),G.end());

    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            int s=sum[i]-sum[j-1];
            s=id(s);
            if(j>my[s].R){
                my[s].R=i;
                my[s].num++;
                my[s].ve.push_back({j,i});
            }
        }
    }
    int ans=0,p;
    for(int i=0;i<G.size();i++){
        if(my[i].num>ans){
            ans=my[i].num;
            p=i;
        }
    }
    cout<<ans<<endl;
    for(auto i:my[p].ve){
        cout<<i.first<<" "<<i.second<<endl;
    }

    return 0;
}

G - Privatization of Roads in Treeland (树)

思路

首先答案肯定是第k+1大的度数

然后就是构造这个树了，我们需要一个可以让颜色不重复的方案，那我们就直接bfs下去就行

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int n,k;
#define bug cout<<"he"<<endl;
int ind[maxn];

int Next[maxn<<1],Laxt[maxn],To[maxn<<1],cnt;
int edge[maxn],road[maxn<<1],id[maxn<<1];

void add(int u,int v,int i){
    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v,id[cnt]=i;
}

int maxdu;

void bfs(){
    queue<int>Q;
    Q.push(1);
    memset(edge,-1,sizeof(edge));
    edge[1]=-1;
    while(!Q.empty()){
        int now=Q.front();
        Q.pop();
        int kk=edge[now];
        for(int i=Laxt[now];i;i=Next[i]){
            if(edge[To[i]]!=-1||To[i]==1)continue;
            edge[To[i]]=road[id[i]]=(++kk)%maxdu;
           // cout<<"id="<<id[i]<<endl;
            Q.push(To[i]);
        }
    }
}

int main(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,i);
        add(v,u,i);
        ind[u]++;ind[v]++;
    }
    sort(ind+1,ind+1+n,greater<int>());
    maxdu=ind[k+1];
    cout<<maxdu<<endl;
    bfs();
    for(int i=1;i<n;i++){
        cout<<road[i]+1<<" ";
    }
    return 0;
}

Diposting di | Edited on

传送门

A - Nastya Is Reading a Book (签到)

题意

给出每一章的页数范围，然后告诉你当前看到那一页，求还没看完的章节数目

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
int l[maxn],r[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
    int k;
    scanf("%d",&k);
    int num=n+1;
    for(int i=1;i<=n;i++){
        if(k>r[i])continue;
        else{
            num=i;
            break;
        }
    }
    cout<<n-num+1<<endl;
    return 0;
}

B - Nastya Is Playing Computer Games (模拟)

题意

一排井盖，井盖下面有金币，你需要拿走所有金币，拿走井盖下的金币需要井盖上没有石头

一开始井盖上面都有一个石头。

每一秒你可以进行以下一种操作

1：向左走或者向右走，

2：把一个石头扔到其他任意一个井盖上面

3：取走金币

现在给你起始位置和井盖个数

问你把所有金币取走需要多少步

思路

很明显的一个贪心策略，可以把所有石头都扔到一个不需要的井盖上面 但是第一个扔的还需要再扔回去

然后因为可能要会出生在中间点，所以可以贪心的选择先向左还是向右走

首先 扔石头肯定需要扔n+1次 ，金币也需要捡n次，走路也需要走n-1次 然后就是重复走的距离min(n-k,k-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    if(n==1||n==k)printf("%d\n",n*3);
    else{
        int sum=3*n;
        sum+=min((k-1),(n-k));
        printf("%d\n",sum);
    }
    return 0;
}

C - Nastya Is Transposing Matrices (神奇)

题意

矩阵a和b 每次可以把a的一个子矩阵按照左对角线翻转，问你能否使a变成b

思路

一开始题目的反转理解错了没想到，

后来发现 如果对于一个2*2的矩阵一次反转就相当于把左下和右上对调。所以只需要保证这一条线的值都相同就肯定可以通过反转变成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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
vector<int>v1[500*500+5];
vector<int>v2[500*500+5];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int a;
            scanf("%d",&a);
            v1[i+j].push_back(a);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int a;
            scanf("%d",&a);
            v2[i+j].push_back(a);
        }
    }

    for(int i=1;i<=n+m;i++){
        sort(v1[i].begin(),v1[i].end());
        sort(v2[i].begin(),v2[i].end());
        if(v1[i]!=v2[i])puts("NO"),exit(0);
    }
    puts("YES");
    return 0;
}

D - Nastya Is Buying Lunch (贪心)

题意

给出一个1-n的数列，然后给你m个关系 如果前面的数正好在后面的数前面一个位置，那么就可以把这两个数交换位置

问你最多可以让最后一个数(a[n])向前走多少步

思路

首先我们可以把点分成两类。

1：可以让n和她交换位置

2：不可以让n和她交换位置

那么题目就是让n最后能有多少个连续的1类点

所以我们考虑贪心能不能把经可能多的一类点向后移动

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=6e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int a[maxn];
map<int,int>mp[maxn];
int vis[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        mp[u][v]=1;
        if(v==a[n])vis[u]=1;
    }
    for(int i=n-1;i>=1;i--){
        if(vis[a[i]]){
            for(int j=i+1;j<n;j++){
                if(mp[a[j-1]].find(a[j])!=mp[a[j-1]].end()){
                    swap(a[j],a[j-1]);
                }
                else break;
            }
        }
    }
    int ans=0;
    for(int i=n-1;i>=1;i--){
        if(vis[a[i]])ans++;
        else break;
    }
    printf("%d\n",ans);
    return 0;
}

E - Nastya Hasn’t Written a Legend （线段树）

题意

给你两个序列 $a_1,a_2\dots a_n$ 和 $ k_1,k_2,\dots k_{n-1}$,输入保证$ a_{i}+k_{i}<=a_{i-1}$.

两种操作:

1：区间求$ \sum_{i=l}^{r}a_i$

2：给单点$ a_i$加$x$ 同时会有连锁反应，若$a_p+k_p>a_{p+1}$,则$a_{p+1}$ 更新为$ a_p+k_p$ ，同理更新到$a_p+2$ 知道不能更新

思路

来自群友的做法 （感谢这位巨佬）

首先根据题意会发现一个式子

给$p$位置加上值$x$ 之后,$a_p-\sum_{i=1}^{p-1}k_i$也增加了x。更新之前已知$a_p-\sum_{i=1}^{p-1}k_i\leq a_{p+1}-\sum_{i=1}^{p}k_i$ 如果$a_p+k_p+x >a_{p+1}$

那么$a_{p+1}=a_p+k_p+x$ 并且$a_{p+1}-\sum_{i=1}^{p}k_i=a_p-\sum_{i=1}^{p}k_i+x$ $a_{p+2} $同理

最后：

我们令$b_x=a_x-\sum_{i=1}^{x-1}k_i$,我们给$p$单点加上$x$之后的效果：就是把$i\in[p+1,n]$ 内所有小于$b_p+x$的值赋值为$b_p+x$

所有修改我们已经搞定了，用线段树或者其他数据结构维护就可以了，求和就是$\sum_{i=l}^{r}b_i+\sum_{i=l}^{r}\sum_{j=1}^{i-1}k_j$ 更新就是区间赋值了，因为$b_x$ 满足单调不减性所以直接二分查找右端点

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int n,m;
ll a[maxn],k[maxn],ks[maxn];
struct SegTree{
    ll sum[maxn<<2],flag[maxn<<2];
    void build(int o,int l,int r){
        flag[o]=inf;
        if(l==r){
            sum[o]=a[l]-k[l-1];return;
        }
        int mid=(l+r)/2;
        build(o<<1,l,mid);
        build(o<<1|1,mid+1,r);
        sum[o]=sum[o<<1]+sum[o<<1|1];
    }
    void push_down(int o,int l,int r){
        if(flag[o]==inf)return;
        int mid=(l+r)/2;
        flag[o<<1]=flag[o<<1|1]=flag[o];
        sum[o<<1]=flag[o]*(mid-l+1);
        sum[o<<1|1]=flag[o]*(r-mid);
        flag[o]=inf;
    }
    void update(int o,int l,int r,int ql,int qr,ll v){
        if(ql<=l&&r<=qr){
            flag[o]=v;
            sum[o]=v*(r-l+1);
            return;
        }
        int mid=(l+r)/2;
        push_down(o,l,r);
        if(ql<=mid)update(o<<1,l,mid,ql,qr,v);
        if(qr>mid)update(o<<1|1,mid+1,r,ql,qr,v);
        sum[o]=sum[o<<1]+sum[o<<1|1];
    }
    ll query(int o,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return sum[o];
        int mid=(l+r)/2;
        push_down(o,l,r);
        ll res=0;
        if(ql<=mid)res+=query(o<<1,l,mid,ql,qr);
        if(qr>mid)res+=query(o<<1|1,mid+1,r,ql,qr);
        return res;
    }
}segtree;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<n;i++)scanf("%lld",&k[i]);
    for(int i=2;i<n;i++)k[i]+=k[i-1];
    for(int i=1;i<n;i++)ks[i]=ks[i-1]+k[i];
    segtree.build(1,1,n);
    scanf("%d",&m);
    while(m--){
        char op[5];int l,r;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='s')printf("%lld\n",segtree.query(1,1,n,l,r)+ks[r-1]-(l>=2?ks[l-2]:0));
        else{
            int L=l,R=n,mid,ans=l;
            ll sum=segtree.query(1,1,n,l,l)+r;
           // cout<<"sum="<<sum<<endl;
            while(L<=R){
                mid=(L+R)/2;
               // cout<<"mid="<<mid<<endl;
                if(sum>segtree.query(1,1,n,mid,mid)){
                    ans=mid;
                    L=mid+1;
                }
                else
                    R=mid-1;
            }
           // cout<<"ans="<<ans<<endl;
            segtree.update(1,1,n,l,ans,sum);
        }
    }
    return 0;
}

Diposting di | Edited on

传送门

A - Sushi for Two(签到)

题意

在一个 01 序列中找出长为偶数的连续的一段使得它前一半和后一半内部分别相同，而前一半和后一半不同。

思路

纸上模拟了一下然后预处理 赛后发现太麻烦了

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const int inf=1e9;
typedef unsigned long long ull;
int a[maxn];
int one[maxn];
int zero[maxn];
int num[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1)one[i]++;
        else zero[i]++;
    }
    for(int i=1;i<=n;i++){
        if(one[i])one[i]=one[i-1]+1;
        if(zero[i])zero[i]=zero[i-1]+1;
     //   cout<<one[i]<<" "<<zero[i]<<endl;
    }
    for(int i=n;i>=1;i--){
        if(one[i])one[i]=max(one[i],one[i+1]);
        if(zero[i])zero[i]=max(zero[i],zero[i+1]);
    }
  //  cout<<endl;
    int ans=0;
    for(int i=1;i<=n;i++){
     //   cout<<one[i]<<" "<<zero[i]<<endl;
        ans=max(ans,min(one[i-1],zero[i]));
        ans=max(ans,min(zero[i-1],one[i]));
    }
    cout<<ans*2<<endl;

    return 0;
}

B - Circus (数学，推公式)

题意

有 n个人，需要把它们分成两组，每组恰好 2/n 个人。每个人可能会技能 11或技能 2，一个人可能会其中一种、两种都会或什么都不会。

要求第一组中会技能 1的人数恰好等于第二组中会技能 2 的人数，输出方案

2<=n<=5000

思路

比赛在纸上写了两张纸都没写出来的题

参考https://www.cnblogs.com/wjyyy/p/cf1138.html 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
vector<int>v[5];
char s[maxn],t[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s%s",s+1,t+1);
    for(int i=1;i<=n;i++){
        v[s[i]-'0'+(t[i]-'0')*2].push_back(i);
    }
    int a=v[0].size(),b=v[1].size(),c=v[2].size(),d=v[3].size(),h=n/2;
    for(int i=0;i<=d;i++){
        if(d-i+c>h||i+b>h)continue;
        if(i<d-i){
            if(b<d-2*i)continue;
            for(int j=0;j<i;j++)
                printf("%d ",v[3][j]);
            h-=i;
            for(int j=0;j<d-2*i;j++)
                printf("%d ",v[1][j]);
            h-=d-2*i;
            for(int j=0;j<c;j++)
                printf("%d ",v[2][j]);
            h-=c;
            for(int j=0;j<h;j++)
                printf("%d ",v[0][j]);
            return 0;
        }
        else{
            if(c<2*i-d)continue;
            c-=2*i-d;
            for(int j=0;j<i;++j)
                printf("%d ",v[3][j]);
            h-=i;
            for(int j=0;j<c;++j)
                printf("%d ",v[2][j]);
            h-=c;
            for(int j=0;j<h;++j)
                printf("%d ",v[0][j]);
            return 0;
        }
    }
    printf("-1");
    return 0;
}

C - Skyscrapers (离散化+贪心)

题意

有一个 n×m的矩阵 aijaij。

对于每个 (i,j)1≤i≤n1≤i≤n），你把第 i行和第 j 列单独抽出，这样就有 n+m−1 个数被你抽出。

你可以对这些数重新标号为正整数，但是要满足第 i行所有数的大小关系不变，第 j列所有数的大小关系不变（两个限制相互独立）。

满足这个限制下，你希望最大的标号尽量小，对每个 (i,j) 求出这个最小的最大标号。

思路

因为行大小关系不变，列大小关系不变，我们考虑分别离散化每行每列，并统计每个数在行内和列内的排名。

然后贪心取个最大的

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const int inf=1e9;
typedef unsigned long long ull;
vector<int>ve;
int a[1500][1500];
vector<int>h[1500];
vector<int>l[1500];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            h[i].push_back(a[i][j]);
            l[j].push_back(a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        sort(h[i].begin(),h[i].end());
        h[i].erase(unique(h[i].begin(),h[i].end()),h[i].end());
    }

    for(int i=1;i<=m;i++){
        sort(l[i].begin(),l[i].end());
        l[i].erase(unique(l[i].begin(),l[i].end()),l[i].end());
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int A=h[i].size(),aa=lower_bound(h[i].begin(),h[i].end(),a[i][j])-h[i].begin()+1;
            int B=l[j].size(),b=lower_bound(l[j].begin(),l[j].end(),a[i][j])-l[j].begin()+1;
            cout<<(aa<b?max(B,b+A-aa):max(A,aa+B-b))<<" ";
        }
        cout<<endl;
    }
    return 0;
}

D - Camp Schedule (KMP 贪心)

题意

有两个 01 串 s 和 t，要求重新排列 s 使得 t 在重新排列后的 s 中出现次数尽量多（位置相交的出现也算）。

思路

一眼KMP 求出T的next数组，然后贪心重叠匹配 关键是可以位置相交

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const int inf=1e9;
typedef unsigned long long ull;
char s[maxn];
char t[maxn];
void kmp_pre(char x[],int m,int next[]){
    int i,j;
    j=next[0]=-1;
    i=0;
    while(i<m){
        while(-1!=j&&x[i]!=x[j])j=next[j];
        next[++i]=++j;
    }
}
int mynext[maxn];
int kmp(char x[],int m,char y[],int n){
    int i,j;
    int ans=0;
    kmp_pre(x,m,mynext);
    i=j=0;
    while(i<n){
        while(-1!=j&&y[i]!=y[j])j=mynext[j];
        i++;j++;
        if(j>=m){
            ans++;
            j=mynext[j];
        }
    }
    return j;
}
string str;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>s;
    cin>>t;
    int lens=strlen(s);
    int a0=0,a1=0;
    for(int i=0;i<lens;i++)if(s[i]=='0')a0++;else a1++;
    int lent=strlen(t);
    kmp_pre(t,lent,mynext);
    int num=mynext[lent];
    //int num=kmp(t,lent,t,lent);
    string p="";
    int n1=0,n0=0;
    for(int i=num;i<lent;i++){
        p+=t[i];
        if(t[i]=='0')n0++;
        else n1++;
    }
    int b1=0,b0=0;
    for(int i=0;i<lent;i++){
        if(t[i]=='0')b0++;
        else b1++;
    }
    if(a0<b0||a1<b1){
        cout<<s<<endl;exit(0);
    }
    str+=t;
    a1-=b1;a0-=b0;
    while(a1>=n1&&a0>=n0){
        str+=p;
        a1-=n1,a0-=n0;
    }
    while(a1--){
        str+="1";
    }
    while(a0--){
        str+="0";
    }
    cout<<str<<endl;
    return 0;
}

F - Cooperative Game (Floyd判环，龟兔赛跑算法)

题意

一个条路 连着一个环，路和环的连接点定义为终点

十个人 每次可以移动一些人向前单项移动（参考链表）

交互题，每次选择一个人的编号让他想前移动

之后系统会告诉你现在哪些点有人，分别是谁

把所有人移动到终点就输出“done”结束

思路

裸的Floyd算法 过程完全一模一样

首先让两个人一个一次移动一步，一个一次移动两步。

然后两人会在一个点相遇。次数假设慢的人经过的距离为$s$ 那么快的人距离为$2s$

$s=m+i*l+k$ 1式

$2s=m+j*l+k$ 2式

两式相减

$s=(j-i)l$ 3式

带入1式

所以当一个点开始从m走到起点时，另一个点也走到了开始的地方

我的想法

1
2
3
假设出发起点到环起点的距离为m，已经确定有环，环的周长为n，（第一次）相遇点距离环的起点的距离是k。那么当两者相遇时，慢指针（t）移动的总距离i = m + a * n + k，快指针（h）的移动距离为2i，2i = m + b * n + k。其中，a和b分别为t和h在第一次相遇时转过的圈数。让两者相减（快减慢），那么有i = (b - a) * n。即i是圈长度的倍数。

将一个指针移到出发起点S，另一个指针仍呆在相遇节点M处两者同时移动，每次移动一步。当第一个指针前进了m，即到达环起点时，另一个指针距离链表起点为i + m。考虑到i为圈长度的倍数，可以理解为指针从链表起点出发，走到环起点，然后绕环转了几圈，所以第二个指针也必然在环的起点。即两者相遇点就是环的起点。
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
int t;
void get(){
    fflush(stdout);
    scanf("%d",&t);
    for(int i=1;i<=t;i++)scanf("%*s");
}
int main()
{
    do{
        puts("next 0 1"),get();
        puts("next 0"),get();
    }while(t==3);
    do{
        puts("next 0 1 2 3 4 5 6 7 8 9"),get();
    }while(t==2);
    puts("done");
    return 0;
}

Diposting di | Edited on

传送门

A.Sea Battle (签到)

题意

给你一个上下两个矩形,让他们左边对着拼起来，求出他们外面一圈的面积

思路

关键就是中间那一块留面积大的就行

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=0;
    ans+=(a+2)*(b+1);


    ans+=(c+2)*(d+1);

    ans-=min(a+2,c+2);

    ans+=max(a+2,c+2);
    ans-=a*b+c*d;
    cout<<ans;
    return 0;
}

B.Draw! (模拟)

题意

按顺序给你一堆比分，问你最多能出现几场胜场

思路

也是直接模拟，不过要注意平局的时候

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll ans=1;
    int n;
    cin>>n;
    ll aa=0,bb=0;
    for(int i=1;i<=n;i++){
        ll a,b;
        cin>>a>>b;
        if(a<bb||b<aa){
            aa=a,bb=b;continue;
        }
        ans+=min(a,b)-max(aa,bb)+1;
        if(aa==bb)ans--;
        aa=a,bb=b;
    }
    cout<<ans;
    return 0;
}

C.Birthday (模拟)

题意

给你一堆高度，让你重新排成一个圆使得对于任意一个高度她周围的差尽可能小

思路

对于一个数，那么她周围的肯定是和他最近的数，所以直接排序一下，拿一个双端队列前后模拟一下就行

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    deque<int>dq;
    for(int i=1;i<=n;i++){
        if(i&1)
            dq.push_back(a[i]);
        else dq.push_front(a[i]);
    }
    for(int i=1;i<=n;i++){
        cout<<dq.front()<<" ";
        dq.pop_front();
    }
    return 0;
}

D.Gourmet choice (并查集缩点+拓扑排序)

题意

有N+M个数 给出他们之间两两的比较，让你构造出一组数据满足这个比较

思路

首先考虑’=’如果有=的话说明他们的值是一样的 所以可以把他们缩成一个点，可以减少计算量

然后对于‘>’和”<”其实我们都可以转化成’>’ 对于一个>我们可以变成一个图，表示>右边的那个数比左边的小，连小一条线，说明左边的要等右边的数字都分配完再分配

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m;
int fa[maxn],d[maxn],a[maxn];
vector<int>G[maxn];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
char s[2005][2005];
void add(int i,int j){
    int aa=find(i),bb=find(j);
    if(aa==bb)puts("No"),exit(0);
    d[aa]++;
    G[bb].push_back(aa);
}
int vis[maxn];
void topo(){
    queue<pair<int,int> >Q;
    for(int i=1;i<=n+m;i++){
        int aa=find(i);
        if(!d[aa]&&!vis[aa])Q.push(make_pair(aa,1)),vis[aa]=1;
    }
    while(!Q.empty()){
        pair<int,int> now=Q.front();Q.pop();
        int u=now.first;
        a[u]=max(a[u],now.second);
        for(auto i:G[u]){
            a[i]=max(a[u]+1,a[i]);
            d[i]--;
            if(!d[i])Q.push(make_pair(i,a[i]));
        }
    }
    for(int i=1;i<=n+m;i++)
        if(d[i])puts("No"),exit(0);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n+m;i++)fa[i]=i;
    for(int i=1;i<=n;i++){
        cin>>s[i]+1;
        for(int j=1;j<=m;j++){
            if(s[i][j]=='='){
                int aa=find(i),bb=find(j+n);
                fa[bb]=aa;
            }
           /* else if(s[j]=='>'){
                add(i,j+n);
            }
            else add(n+j,i);*/
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
        if(s[i][j]=='>')add(i,n+j);
        if(s[i][j]=='<')add(n+j,i);
        }
    topo();
    cout<<"Yes"<<endl;
    for(int i=1;i<=n;i++)cout<<a[find(i)]<<" ";cout<<endl;
    for(int j=1;j<=m;j++)cout<<a[find(j+n)]<<" ";
    return 0;
}
/*
3 3
<<<
<<=
<<=
*/

E.String Multiplication(DP)

题意

定义一种字符串乘法 如果aab*c变成cacacbc

就是用后一个字符串填满前一个字符串的空隙和前后

问你n个乘法过后的结果字符串的最长连续相同字母是多少

思路

可以发现答案又最后一种字符串控制，因为就算前面的答案是多少都会被最后一个字符串拆开

所以分析最后一个字符串，发现情况有三种

如果最后一个字符串字符只有一种，那么答案就为这个前面那个字符串的这个字符长度+1 并且乘上最后一个字符串的长度 + 前面那个字符串的长度

如果是 不是的话那么答案就只和最后字符串的前后字符有关系，答案就是当前字符串的前后最长长度+（前面的答案是否有包含这个字符） 如果前后的字符都一样的话那么答案又不同了

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int dp[maxn][26],a[26],head,tail,ans;
char s[maxn];
void init(){
    memset(a,0,sizeof(a));
    int n=strlen(s+1),t=1;
    for(int i=2;i<=n;i++){
        if(s[i]!=s[i-1])
            a[s[i-1]-'a']=max(a[s[i-1]-'a'],t),t=1;
        else t++;
    }
    a[s[n]-'a']=max(a[s[n]-'a'],t);
    head=tail=1;
    for(int i=2;i<=n;i++)
        if(s[i]==s[i-1])head++;
        else break;
    for(int i=n-1;i>=1;i--)
        if(s[i]==s[i+1])tail++;
    else break;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s+1;
        int len=strlen(s+1);
        init();
        if(head==len){
            int k=s[1]-'a';
            dp[i][k]=head*(dp[i-1][k]+1)+dp[i-1][k];
        }
        for(int j=0;j<26;j++){
            dp[i][j]=max(dp[i][j],a[j]);
            if(dp[i-1][j]){
                dp[i][j]=max(dp[i][j],1);
                int p1=0,p2=0;
                if(s[1]==char('a'+j)){
                    p1=1;
                    dp[i][j]=max(dp[i][j],head+1);
                }
                if(s[len]==char('a'+j)){
                    p2=1;
                    dp[i][j]=max(dp[i][j],tail+1);
                }
                if(p1&&p2)dp[i][j]=max(dp[i][j],head+tail+1);
            }
            if(i==n)ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

F.Asya And Kittens （启发式合并 or ripe黑科技 or 链表操作）

题意

给你n-1对，相邻的在一块，选了这两个数，这两个集合就可以看成一个集合了，问符合条件的序列。

思路

很容易想到并查集的合并操作，对于一次合并相当于把两个集合变成了一块，那么现在的问题就是怎么处理集合合并

方法有三，

1.启发式合并，每次把容量小的合并到容量大的里面去，这样可以保证复杂度是log

2.链表，这样直接把头指针插到另一个的尾指针上，每一个的操作复杂度为o(1)

3.rope 黑科技，

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int fa[maxn];
vector<int>G[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        fa[i]=i;G[i].push_back(i);
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        int fx=fa[x],fy=fa[y];
        if(G[fx].size()<G[fy].size())swap(fx,fy);
        for(int j=0;j<G[fy].size();j++){
            G[fx].push_back(G[fy][j]);
            fa[G[fy][j]]=fx;
        }
        G[fy].clear();
    }
    for(int i=0;i<n;i++){
        cout<<G[fa[1]][i]<<" ";
    }
    return 0;
}

rope

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
#include<bits/stdc++.h>
#include<ext/rope>
using namespace __gnu_cxx;
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
rope<int>a[maxn];
int fa[maxn];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        a[i].push_back(i);
        fa[i]=i;
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        x=find(x),y=find(y);
        a[x]+=a[y];
        fa[y]=x;
    }
    for(int i=1;i<=n;i++){
        if(find(i)==i){
            for(int j=0;j<a[i].size();j++)cout<<a[i][j]<<" ";
        }
    }
    return 0;
}

Diposting di | Edited on

传送门

A.Got Any Grapes? (水题)

手冷把y写成x被fst了

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int x,y,z,a,b,c;
    cin>>x>>y>>z;
    cin>>a>>b>>c;
    if(a<x){
        cout<<"NO"<<endl;exit(0);
    }
    a-=x;
    b=a+b;
    if(b<y){
        cout<<"NO"<<endl;return 0;
    }
    b-=y;
    c+=b;
    if(c<z){
        cout<<"NO"<<endl;return 0;
    }
    cout<<"YES"<<endl;
    return 0;
}

B.Yet Another Array Partitioning Task (毒瘤？)

题意

让你分出k个区间，每个区间至少m个数，然后取每个区间的前m个最大值相加，使值最大

思路

本质就是求前m*k大的数,然后我们就可以把前m×k大的数求出来 然后记录坐标，然后连续m个分为一组即可

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
    ll value;
    int id;
    bool operator<(const node &a)const{
        return value>a.value;
    }
}my[maxn];
bool f[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    ll m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>my[i].value,my[i].id=i;
    sort(my+1,my+1+n);
    ll ans=0;
    for(ll i=1;i<=m*k;i++){
        ans+=my[i].value;f[my[i].id]=1;
    }
    cout<<ans<<endl;
    for(int i=1,t=0,p=0;i<=n;i++){
        if(f[i]){
            t++;
            if(t==m){
                cout<<i<<" ";t=0;
                p++;
                if(p==k-1)return 0;
            }
        }
    }
    return 0;
}

C. Trailing Loves (or L’oeufs?) (质因子分解)

题意

求n!在b进制下末尾0的个数

思路

只要会十进制下求n！的就会这题了

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll prime[maxn][2];
int tot;
ll hello(ll n,ll p){
    ll ans=0;
    while(n){
        ans+=n/p;
        n/=p;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll n,m;
    cin>>n>>m;
    for(ll i=2;i<=sqrt(m);i++){
        if(m%i==0){
            prime[++tot][0]=i;
            while(m%i==0){
                m/=i;
                prime[tot][1]++;
            }
        }
    }
    if(m!=1){
        prime[++tot][0]=m;prime[tot][1]=1;
    }
    ll ans=inf;
    for(int i=1;i<=tot;i++){
            ans=min(ans,hello(n,prime[i][0])/prime[i][1]);
    }
    cout<<ans<<endl;
    return 0;
}

D.Flood Fill (区间DP，本质求LCS，记忆化搜索)

题意

一个颜色序列，每个位置有一个颜色，选择一个起始位置，每次可以改变左右的一段颜色段（如果左边和右边颜色一样就一起改变），把整段变成一种颜色， 问最少操作多少次。n<=5000

思路

首先一整段颜色段肯定没用,我们可以缩点，简化题意

然后想到区间DP（石子合并） 但是石子合并是可以任意起点，而这题固定起点了，

所以可以把区间DP的n^3变成n^2了，我区间DP很差所以比赛只想出来记忆化搜索

记忆化搜索对付这种只有终点没有起点的题真的是屡试不爽

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int c[maxn];
int a[maxn];
int dp[5500][5500];
int dfs(int l,int r){
    if(dp[l][r]!=-1)return dp[l][r];
    int ans=0;
    if(l==r)return 0;
    if(a[l]==a[r])ans=dfs(l+1,r-1)+1;
    else ans=min(dfs(l+1,r),dfs(l,r-1))+1;
    dp[l][r]=ans;
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    a[1]=c[1];int cnt=1;
    for(int i=2;i<=n;i++){
        if(a[cnt]!=c[i]){
            a[++cnt]=c[i];
        }
    }
  /*  for(int i=1;i<=cnt;i++){
        cout<<a[i]<<" ";
    }*/
    memset(dp,-1,sizeof(dp));
    cout<<dfs(1,cnt)<<endl;
    return 0;
}

E.Arithmetic Progression (mt19937+交互题+二分找最大值+随机数取GCD)

题意

你电脑中有一个等差数列,你有两种循环

1.问这个数列的第x项的值

2.问是否有一个项的值比X大

让你在60次内找出这个等差数列的首项和公差

思路

很明显可以在32次内得出最大值，然后就是求公差了，

我们既然有了最大值，那我们就可以求出任意一项和最大值的差值肯定是公差的倍数

然后我们就直接对这些差值求GCD

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,k,m,ti=60;
mt19937_64 lwt(time(0));
int ask(int x){
    cout<<"? "<<x<<endl;
    cin>>k;
    return k;
}
int ask2(int x){
    cout<<"> "<<x<<endl;
    cin>>k;
    ti--;
    return k;
}
int find_max(){
    int l=-1,r=1e9;
    int ans;
    while(r-l>=0){
        int mid=(l+r)/2;
        if(ask2(mid))l=mid+1;else r=mid-1,ans=mid;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n;
    m=find_max();
    int d=0;
    for(int i=1;i<=ti;i++){
        int id=lwt()%n+1;
        int x=ask(id);
        if(x!=m)d=__gcd(d,m-x);
    }
    cout<<"! "<<m-(n-1)*d<<" "<<d<<endl;
    return 0;
}

F.Please, another Queries on Array? (线段树区间乘+欧拉函数+bitset)

题意

两个操作

1.把一个区间乘上一个值X

2.求一个区间的欧拉函数

思路

看到区间乘法很容易想到线段树

那么欧拉函数怎么求，很明显欧拉函数和素因子个数有关

发现每个x都小于等于300 打表发现300内的素因子只有62个

然后就是怎么记录这几个素因子的问题了，你可以用LL的位数或者bitset记录

（或者用数组？那可能会超时吧）

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=4e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,q;
bool isprime[500];
ll prime[500];
ll inv[500];
ll Pow(ll a,ll i){
    ll s=1LL;
    while(i){
        if(i&1)s=1LL*s*a%mod;
        a=1LL*a*a%mod;
        i>>=1;
    }
    return s;
}
int init(int n){
    int p=0;
    for(int i=0;i<=n;i++)isprime[i]=true;
    isprime[0]=isprime[1]=false;
    for(int i=2;i<=n;i++){
        if(isprime[i])prime[p++]=i*1LL;
        for(int j=0;j<p;j++){
            if(prime[j]*i>n)break;
            isprime[prime[j]*i]=false;
            if(i%prime[j]==0)break;
        }
    }
    return p;
}
ll a[maxn];
struct segtree{
    bitset<62>has[maxn<<2];
    bitset<62>laz[maxn<<2];
    ll ans[maxn<<2];
    ll lazy[maxn<<2];
    void pushup(int o){
        ans[o]=1LL*ans[o<<1]*ans[o<<1|1]%mod;
        has[o]=has[o<<1]|has[o<<1|1];
    }
    void pushdown1(int o,int l,int r){
        if(lazy[o]==1)return;
        int mid=(l+r)/2,len1=mid-l+1,len2=r-mid;
        lazy[o<<1]=1LL*lazy[o<<1]*lazy[o]%mod;
        ans[o<<1]=1LL*ans[o<<1]*Pow(lazy[o],len1)%mod;
        lazy[o<<1|1]=1LL*lazy[o<<1|1]*lazy[o]%mod;
        ans[o<<1|1]=1LL*ans[o<<1|1]*Pow(lazy[o],len2)%mod;
        lazy[o]=1;
    }
    void pushdown2(int o){
        laz[o<<1]|=laz[o];
        has[o<<1]|=laz[o];
        laz[o<<1|1]|=laz[o];
        has[o<<1|1]|=laz[o];
        laz[o].reset();
    }
    void build(int o,int l,int r){
        lazy[o]=1;has[o].reset();laz[o].reset();
        if(l==r){
            ans[o]=a[l];
            for(int i=0;i<62;i++)if(a[l]%prime[i]==0)has[o].set(i);
            return;
        }
        int mid=(l+r)/2;
        build(o<<1,l,mid);build(o<<1|1,mid+1,r);
        pushup(o);
    }
    void update(int o,int l,int r,int ql,int qr,ll v,bitset<62> bit){
        if(ql<=l&&r<=qr){
            lazy[o]=1LL*lazy[o]*v%mod;
            ans[o]=1LL*ans[o]*Pow(v,r-l+1)%mod;
            laz[o]|=bit;has[o]|=bit;
            return;
        }
        pushdown1(o,l,r);
        pushdown2(o);
        int mid=(l+r)/2;
        if(ql<=mid)update(o<<1,l,mid,ql,qr,v,bit);
        if(qr>mid)update(o<<1|1,mid+1,r,ql,qr,v,bit);
        pushup(o);
    }
    ll query1(int o,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return ans[o];
        pushdown1(o,l,r);
        int mid=(l+r)/2;
        ll ans=1;
        if(ql<=mid)ans=ans*query1(o<<1,l,mid,ql,qr)%mod;
        if(qr>mid)ans=ans*query1(o<<1|1,mid+1,r,ql,qr)%mod;
        return ans;
    }
    bitset<62> query2(int o,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return has[o];
        pushdown2(o);
        int mid=(l+r)/2;
        bitset<62> ans;ans.reset();
        if(ql<=mid)ans|=query2(o<<1,l,mid,ql,qr);
        if(qr>mid)ans|=query2(o<<1|1,mid+1,r,ql,qr);
        return ans;
    }

}seg;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int p=init(300);
    for(int i=0;i<p;i++)inv[i]=Pow(1LL*prime[i],mod-2);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    seg.build(1,1,n);
    while(q--){
        int l,r;
        ll x;char str[10];
        cin>>str;
        if(str[0]=='T'){
            cin>>l>>r;
            ll res=seg.query1(1,1,n,l,r);
            bitset<62> bit=seg.query2(1,1,n,l,r);
            for(int j=0;j<62;j++)
                if(bit[j])res=(1LL*res*inv[j]%mod*(prime[j]-1+mod)%mod)%mod;
            cout<<res<<endl;
        }
        else{
            cin>>l>>r>>x;
            bitset<62>bit;bit.reset();
            for(int j=0;j<62;j++)if(x%prime[j]==0)bit.set(j);
            seg.update(1,1,n,l,r,x,bit);
        }
    }
    return 0;
}

Diposting di | Edited on

传送门

前四题签到题不讲，

E.Lunar New Year and Red Envelopes (DP+数据结构)

题意

有k个红包，每个红包可以在一个时间段拿起，并且在拿起之后知道D时间都不能拿其他红包

如果在某一时刻可以拿红包会拿金额最大的，如果金额同样大会拿D最大的，

有m次干扰的机会，可以让在某一时刻不能拿红包。

问最少可以得到多少金额

题意

首先，每一时刻拿哪个红包和时间D都已经固定了，于是我们就直接构造dp转移一下就行

那么对于一个时刻，如果没有红包那么就直接转移到下一时间

如果可以抢红包那么，

然后这题的很多解法的DP都差不多,主要差别是如何获取每一时间的最优金额和D的，

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+20;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll dp[maxn][205];
int n,m,k;
struct node{
    int w,d;
    void add(int ww,int dd){
        if(ww>w)w=ww,d=dd;
        if(ww==w&&dd>d)d=dd;
    }
}my[maxn<<2];
void down(int i){
    my[i<<1].add(my[i].w,my[i].d);
    my[i<<1|1].add(my[i].w,my[i].d);
}
void update(int i,int l,int r,int ql,int qr,int w,int d){
    if(l>=ql&&r<=qr){
        my[i].add(w,d);
        return;
    }
    int mid=(l+r)/2;
    down(i);
    if(ql<=mid)update(i<<1,l,mid,ql,qr,w,d);
    if(qr>mid)update(i<<1|1,mid+1,r,ql,qr,w,d);
}
node query(int i,int l,int r,int pos){
    if(l==r){
        return my[i];
    }
    down(i);
    int mid=(l+r)/2;
    if(pos<=mid)query(i<<1,l,mid,pos);
    else query(i<<1|1,mid+1,r,pos);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++){
        int s,t,d,w;
        cin>>s>>t>>d>>w;
        update(1,1,n,s,t,w,d);
    }
    memset(dp,inf,sizeof(dp));
    for(int i=0;i<=m;i++)dp[1][i]=0;
    for(int i=1;i<=n;i++){
        node now=query(1,1,n,i);
        int w=now.w;int d=now.d;
        for(int j=0;j<=m;j++){
            if(d){
                dp[d+1][j]=min(dp[d+1][j],dp[i][j]+w);
                dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);
            }
            else
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
        }
    }
    ll ans=inf;
    for(int i=0;i<=m;i++)ans=min(ans,dp[n+1][i]);
    cout<<ans<<endl;
    return 0;
}

Diposting di | Edited on

传送门

前四题水题不讲

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
////A
    int q;
    cin>>q;
    while(q--){
        ll l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        cout<<l1<<" ";
        if(l2!=l1)cout<<l2;
        else cout<<r2;
        cout<<endl;
    }
////B
    int n;
    cin>>n;
    int mx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];mx=max(a[i],mx);num[a[i]]++;
    }
    cout<<mx<<" ";
    for(int i=mx;i>=1;i--){
        if(!(mx%i))num[i]--;
    }
    for(int i=mx;i>=1;i--){
        if(num[i]){cout<<i<<endl;return 0;}
    }
////C
char str[maxn];
char s[8][5]={"RGB","RBG","GRB","GBR","BGR","BRG"};
int id=0;
int num[8];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    cin>>str;
    for(int i=0;i<6;i++){
        for(int j=0;j<n;j++){
            if(str[j]!=s[i][j%3])num[i]++;
        }
    }
    int mx=num[0];
    for(int i=0;i<6;i++)if(num[i]<mx)mx=num[i],id=i;
    cout<<mx<<endl;
    for(int i=0;i<n;i++)cout<<s[id][i%3];
////D
 char str[maxn];
char s[5]="RBG";
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,ans=0;
    cin>>n;
    cin>>str;
    for(int i=1;i<n;i++){
        if(str[i]==str[i-1]){
            for(int j=0;j<3;j++){
                if(s[j]!=str[i-1]&&s[j]!=str[i+1]){
                    str[i]=s[j];break;
                }
            }
            ans++;
        }
    }
    cout<<ans<<endl;
    for(int i=0;i<n;i++)cout<<str[i];

E2.Array and Segments (Hard version) (差分/线段树)

题意

给出N个数,M个区间，每次可以把一个区间-1,问选取哪些区间可以使得这组数据的最大最小值相差最大

题解

枚举区间边界,因为区间边界肯定是敏感点，然后把所有有经过这个敏感点的区间都更新进差分数组，再塞入原数组更新答案；复杂度(n*m)

线段树直接枚举区间（n×m×logn）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int lq[maxn],rq[maxn],a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    int mx=-inf,mi=inf,l,r;
    for(int i=1;i<=n;i++){
        cin>>a[i];mx=max(mx,a[i]);mi=min(mi,a[i]);
    }
    ll res=mx-mi;
    vector<int>Q,now,ans;
    for(int i=1;i<=m;i++){
        cin>>lq[i]>>rq[i];
        Q.push_back(lq[i]);
        Q.push_back(rq[i]);
    }
    int sum[maxn];
    sort(Q.begin(),Q.end());
    Q.erase(unique(Q.begin(),Q.end()),Q.end());
    for(int i=0;i<Q.size();i++){
        now.clear();
        memset(sum,0,sizeof(sum));
        for(int j=1;j<=m;j++){
            if(lq[j]<=Q[i]&&rq[j]>=Q[i]){
                now.push_back(j);
                sum[lq[j]]--;
                sum[rq[j]+1]++;
            }
        }
        mx=-inf,mi=inf;
        for(int i=1;i<=n;i++){
            sum[i]+=sum[i-1];
            mx=max(mx,sum[i]+a[i]);
            mi=min(mi,sum[i]+a[i]);
        }
        if(mx-mi>res){
            res=mx-mi;
            ans=now;
        }
    }
    cout<<res<<endl;
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

F.MST Unification (最小生成树)

题意

给出一个图，可以任意增大一条边的权值，问你需要修改几次可以使这个最小生成树唯一

题解

最小生成树权值已固定，那么需要修改的边肯定是权值相同的边，但是权值相同的边又不能都修改

所以针对堆权值相同的边，哪些边是对答案有影响的

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int fa[maxn],r[maxn],n,m;
struct node{
    int u,v,w;
    bool operator<(const node &x)const {
        return this->w<x.w;
    }
};
vector<node>G;
void init(int n){
    for(int i=0;i<=n;i++)fa[i]=i;
}
int find(int x){
    if(x==fa[x])return fa[x];
    else return fa[x]=find(fa[x]);
}
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(x<y)fa[y]=x;
    else fa[x]=y;
}
bool same(int x,int y){
    return find(x)==find(y);
}
int kruskal(){
    sort(G.begin(),G.end());
    int ans=0;
    for(int i=0;i<G.size();){
        vector<node>now;
        int j;
        for(j=i;j<G.size()&&G[j].w==G[i].w;j++){
            if(!same(G[j].u,G[j].v))now.push_back(G[j]);
        }
        i=j;
        for(j=0;j<now.size();j++){
            if(!same(now[j].u,now[j].v))unite(now[j].u,now[j].v);
            else ans++;
        }
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    init(n);
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        G.push_back(node{x,y,z});
    }
    cout<<kruskal()<<endl;
    return 0;
}

Diposting di | Edited on

传送门

A. Splitting into digits（水题)

题解

全部输出1即可

1
2
3
4
5
6
    int n;
    cin>>n;
    cout<<n<<endl;
    for(int i=1;i<=n;i++)cout<<1<<" ";
    return 0;
}

B.Game with string (模拟栈)

一个字符串，如果连续两个一样的字符就削去,有连环效应,问削去次数是奇数还是偶数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    stack<char>st;
    cin>>s;
    int len=s.size();
    int num=0;
    for(int i=0;i<len;i++){
        if(st.empty()||st.top()!=s[i]){
            st.push(s[i]);
        }
        else{
            st.pop();
            num++;
        }
    }
    if(num&1)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

C.Grid gam （傻逼娱乐题）

题意

给出一个4*4的矩阵 每次下来一个1×2或者2×1的矩形，连续一行一列都填满就削去，问你每次把矩形放哪可以保证所有的矩形都能放下

题解

没看懂题意觉得神奇，以为是俄罗斯方块一样，看懂就弱智题,原来是可以制定位置，那就直接把横的放第一排，竖的都放第二三排，这样保证绝对可以削去；

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int mp[16][16];
void finx(){
    if(mp[1][1]==0)cout<<1<<" "<<1<<endl,mp[1][1]=1,mp[1][2]=1;
    else cout<<1<<" "<<3<<endl,mp[1][3]=mp[1][4]=1;
}
void finy(){
    for(int j=1;j<=4;j++){
        if(mp[2][j]==0){
            cout<<2<<" "<<j<<endl;
            mp[2][j]=1;
            mp[3][j]=1;
            return;
        }
    }
}
void earse(){
    if(mp[1][1]&&mp[1][3]){
        for(int i=1;i<=4;i++){
            mp[1][i]=0;
        }
    }
    for(int i=1;i<=4;i++){
        if(mp[2][i]==0)return;
    }
    for(int i=1;i<=4;i++){
        mp[2][i]=mp[3][i]=0;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string s;
    cin>>s;
    int len=s.size();
    for(int i=0;i<len;i++){
        if(s[i]=='1'){
            finx();
            earse();
        }
        else{
            finy();
            earse();
        }
    }
    return 0;
}

D.Game with modulo (二分交互题)

题意

系统有一个a,你每次给出一个x和y

如果x%a>y%a 系统回答”x”，否则回答“y”；(你需要在60次内找出a, a<=1e9)

题解

首先大二分找出x的大区间（如果一大一小两个数%a都返回y说明a不在区间内否则a就在现在的x和y中）

然后小二分 区间,每次限制mid 逼近答案； 因为1e9找出最多30次，小区间最多三十次，所以60次足以

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
char ch;
bool input(){
    cin>>ch;
    if(ch=='y')return true;
    else return false;
}
int x=0,y=1;
bool check(int a,int b){
    cout<<"? "<<a<<" "<<b<<endl;
    //cout<<a%16<<" "<<b%16<<endl;
    if(input())return true;
    else return false;
}
void dfs(){
    while(check(x,y)){
        swap(x,y);
        y=x*2;
    }
    int l=x,r=y;
    while(l+1<r){
        int mid=(l+r)/2;
        if(check(l,mid)){
            l=mid;
        }
        else r=mid;
    }
    cout<<"! "<<r<<endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string s;
    while(cin>>s){
        if(s[0]=='e')break;
        x=0,y=1;
        if(!check(x,y)){
            cout<<"! "<<1<<endl;continue;
        }
        x=1;y=2;
        dfs();
    }
    return 0;
}

E.Johnny Solving( 鸽笼定理)

题意

给出一连通图，不存在自环和重复边，n个点,m条边 并且每个点的度数都大于等于3,给出k；

1：如果这个图满足存在一条路径的长度大于等于n/k就输出”path”并输出路径

2：或者如果这个图有K个长度大于3并且不是3的倍数的环就输出circles ，并且输出环上的点

3：如果都不满足就输出-1；

题解

首先第一个可以直接dfs找出一条路径判断 easy

那么第二个 首先根据鸽笼定理，如果不存在长度为n/k的路径。那么这个图至少有k个叶子结点。

那么有什么用呢， 可以知道对于一个叶子结点并且度大于等于三 可以知道这个叶子结点肯定至少和除了父亲结点之外的两个祖先结点连接，（也就是说每个叶子结点都会在至少两个环内）

于是我们就判断一个叶子结点是否一个长度不为3的环即可；

如果长度都为3呢，那么看图

\QQ图片20190130200943.png)

这个图按照dfs路径是1-2-3-4-5-6-7-8-9 然后对于9这个叶子结点来说 有两个环 9-7-8 和9-8-7-6-5-4

这两个环长度为3的倍数，但是可以看出这两个环又构成了一个新环9-7-6-5-4 这个环的长度就为5 所以是不是很巧妙

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
vector<int> G[maxn];
vector<int> leaves;
int fa[maxn];
int dep[maxn];
int vis[maxn];
void dfs(int u){
    vis[u]=1;
    bool leaf=true;
    for(auto v : G[u]){
        if(vis[v])continue;
        leaf=false;
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs(v);
    }
    if(leaf)
        leaves.push_back(u);
}
void print(int s,int t){
    while(s!=t){
        cout<<s<<" ";
        s=fa[s];
    }
    cout<<t<<endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m,k;
    cin>> n >> m >> k;
    int x,y;
    while(m--){
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dep[1]=1;
    dfs(1);
    int p=n/k;if(n%k)p++;
    for(int i=1;i<=n;i++){
        if(dep[i]>=p){
            cout<<"PATH"<<endl;
            cout<<dep[i]<<endl;
            print(i,1);
            return 0;
        }
    }
    cout<<"CYCLES"<<endl;
    for(auto u :leaves){
        bool flag=false;
        vector<int>pre;
        for(auto v: G[u]){
            if(v==fa[u])continue;
            if((dep[u]-dep[v]+1)%3){
                flag=true;
                cout<<dep[u]-dep[v]+1<<endl;
                print(u,v);
                break;
            }
            else{
                pre.push_back(v);
            }
        }
        if(!flag){
            if(dep[pre[0]]>dep[pre[1]])swap(pre[0],pre[1]);
            cout<<dep[pre[1]]-dep[pre[0]]+2<<endl;
            cout<<u<<" ";
            print(pre[1],pre[0]);
        }
        k--;
        if(k==0)return 0;
    }
    return 0;
}

Diposting di | Edited on

传送门

A. [A - Roman and Browser(水题)

题意

太水不想写

B.Build a Contest (水题)

题意

给出一个n,m, 接下来吗每一时刻出现m个数,如果在某一时刻N种数字都出现过就输出’1’并同时把1-n种数字各删去一个

题解

很明显和每个数出现的最小值有关,如果出现数的最小值都大于等于1代表这n个数都出现过了,那么如何解决删去呢，如果每时刻都判断每个数都是否大于1就太浪费时间了,我们可以用个变量记录已经出现了多少个数,如果达到n再删去，这样复杂度并不会达到(n*m);

同时也可以换方向,如果我不删去呢？

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int a[maxn],mx[maxn];
int flag[maxn];
set<int>st;
int num[maxn];
double pi=acos(-1.0);
void update(int now,int l,int r,int pos){
    if(l==r){
        mx[now]++;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid)update(now<<1,l,mid,pos);
    else update(now<<1|1,mid+1,r,pos);
    mx[now]=min(mx[now<<1],mx[now<<1|1]);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    int k=1;
    for(int i=1;i<=m;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        update(1,1,n,a[i]);
        if(mx[1]==k)k++,cout<<1;
        else cout<<0;
    }

    return 0;
}
//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}

int a[maxn];
int aa[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    int now=1;
    for(int i=1;i<=m;i++){
        int p;
        cin>>p;
        a[p]++;
        aa[a[p]]++;
        if(aa[now]>=n){
            cout<<1;now++;
        }
        else cout<<0;
    }
    return 0;
}

C.NN and the Optical Illusion (简单几何)

一个圆均匀得被许多大小相等的小圆包围给你小圆个数和小圆半径 让你求出大圆半径.

\1548761595468.png)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}

int sx,sy;
struct node{
    int x,y;
    int id;
}my[700];
double pi=acos(-1.0);
int main()
{
   /* std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);*/
  //  cin>>sx>>sy;
  //  for(int i=1;i<=666;i++)cin>>my[i];
    double n,r;
    cin>>n>>r;
    printf("%.7f\n",sin(pi/n)*r/(1.0-sin(pi/n)));
    return 0;
}

D.Dasha and Chess （鸽笼定理）

题意

你操控白棋可以八连通走动，电脑操控黑棋会直接跳到任意没棋的格子，

如果你操纵白棋走到和某个黑棋的行或者列你就赢了

棋盘999*999，黑棋个数666个

题解

首先666/4=166.5

先把棋子挪到中间，这时棋子就会分布在四个方位中,假设最分散的情况 比较多的三个方位中的棋子数肯定是大于或者等于666-166=500个的

然后让棋子往最多棋子的那三个方向中的对角线的走去，因为棋子每次移动都向三个方向都移动一格，相当于同时把三个方向都扫了过去，而500.500到顶点只需要499步，所以肯定会有黑棋跑不掉

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}

int sx,sy;
struct node{
    int x,y;
    int id;
}my[700];
int u,v,w;

int vis[1005][1005];

void go(int x,int y){
    sx+=x;sy+=y;
    if(vis[sx][sy])sx-=x;
    cout<<sx<<" "<<sy<<endl;
    cin>>u>>v>>w;
    if(u==-1)exit(0);
    vis[my[u].x][my[u].y]=0;
    vis[v][w]=1;
    my[u].x=v;my[u].y=w;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>sx>>sy;
    for(int i=1;i<=666;i++)cin>>my[i].x>>my[i].y,vis[my[i].x][my[i].y]=1;
    int ok=1;
    while(sx<500)go(1,0);
    while(sx>500)go(-1,0);
    while(sy<500)go(0,1);
    while(sy>500)go(0,-1);
    int a=0,b=0,c=0,d=0;
    for(int i=1;i<=499;i++)
        for(int j=1;j<=499;j++)a+=vis[i][j];
    for(int i=1;i<=499;i++)
        for(int j=501;j<=999;j++)b+=vis[i][j];
    for(int i=501;i<=999;i++)
        for(int j=1;j<=499;j++)c+=vis[i][j];
    for(int i=501;i<=999;i++)
        for(int j=501;j<=999;j++)d+=vis[i][j];
    int aa=a+b+c,bb=a+b+d,cc=a+c+d,dd=c+b+d;
    int mx=max(max(aa,bb),max(cc,dd));
    if(aa==mx)while(true)go(-1,-1);
    if(bb==mx)while(true)go(-1,1);
    if(cc==mx)while(true)go(1,-1);
    else while(true)go(1,1);
    return 0;
}

E.Andrew and Taxi (二分答案+拓扑判环)

题意

给出一个有向图，让你把一些边反转需要花费费用Ci ,问你把这个图变成一个无环图需要的反转边的最大值最小是多少

题意

问最大最小值那必须是二分答案；

首先可以二分答案，然后把大于答案的边 拿去进行拓扑判断是否有环,如果没环,那么这个答案就是合法的

如果有环说明答案还要加，然后小于答案的边我们就把他们当成双向的就行了，因为题目要输出反转哪些边，所以我们可以记录拓扑序处理一下

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}

int n,m;

struct node{
    int u,v;
    ll c;
}my[maxn];
vector<int>e[maxn];
int in[maxn];
int cnt[maxn];
vector<int>anw;
bool isok(ll mid){
    for(int i=1;i<=n;i++)e[i].clear();
    memset(in,0,sizeof(in));
    for(int i=1;i<=m;i++){
        if(my[i].c>mid)e[my[i].u].push_back(my[i].v),++in[my[i].v];
    }
    queue<int>p;
    int now=0;
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)if(in[i]==0)p.push(i),cnt[i]=++now;
    while(!p.empty()){
        int no=p.front();p.pop();
        for(int i=0;i<e[no].size();i++){
            int nex=e[no][i];
            in[nex]--;
            if(in[nex]==0){
                p.push(nex);
                cnt[nex]=++now;
            }
        }
    }
    for(int i=1;i<=n;i++)if(in[i])return false;
    anw.clear();
    for(int i=1;i<=m;i++){
        if(my[i].c<=mid&&cnt[my[i].u]>cnt[my[i].v]){
            anw.push_back(i);
        }
    }
    return true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    cin>>n>>m;
    ll l=0,r=0;
    for(int i=1;i<=m;i++){
        cin>>my[i].u>>my[i].v>>my[i].c;
        r=max(r,my[i].c);
    }
    ll ans=0;
    while(l<=r){
       ll mid=(l+r)/2;
       if(isok(mid)){
        ans=mid;
        r=mid-1;
       }
       else l=mid+1;
    }
    isok(ans);
    cout<<ans<<" "<<anw.size()<<"\n";
    for(int i=0;i<anw.size();i++)cout<<anw[i]<<" ";
    return 0;
}

F.Ivan and Burgers （线性基）

题意

题意进行翻译就是求出区间的最大异或值了,因为n^(n^a^b^c)==a^b^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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=5e5+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
const int maxbit=32;
int n;

int c[maxn];
int q;
struct node{
    int id;
    int l,r;
    bool operator <(const node &a)const{
        return this->r<a.r;
    }
}Q[maxn];

struct base{
    int num;
    int id;
}my[maxbit];

void ins(int num,int id){
    for(int i=31;i>=0;i--){
        if(num&(1<<i)){
            if(my[i].num==0){
                my[i].id=id;
                my[i].num=num;
                break;
            }
            else if(my[i].id<id){
                swap(my[i].id,id);
                swap(my[i].num,num);
            }
            num^=my[i].num;
        }
    }
}
int ans[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>c[i];
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>Q[i].l>>Q[i].r;Q[i].id=i;
    }
    sort(Q+1,Q+1+q);
    int now=1;
    for(int i=1;i<=q;i++){
        while(now<=Q[i].r)ins(c[now],now),now++;
        for(int j=31;j>=0;j--){
            if(my[j].id>=Q[i].l&&((ans[Q[i].id]^my[j].num)>ans[Q[i].id]))ans[Q[i].id]^=my[j].num;
        }
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
    return 0;
}

Diposting di | Edited on

传送门

A. The Fair Nut and Elevator(水题)

题意

一个楼里有一个电梯，第i层有A[i]人，每个人每天用两次电梯，下楼一次和上楼一次，现在规定电梯初始处于一个点 每次有人需要电梯 ，电梯就上去到这个人的楼 载到一楼再到初始的层数

题解

发现 如果电梯在一楼和在任意一楼的接送花费是一样的，但是如果在一楼， 一楼的人需要电梯就不需要电梯额外跑两次，所以电梯在一楼最优（当然数据很小，你也可以暴力

1
2
3
4
5
int n;
cin>>n;
ll sum=0;
for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i]*2LL*(i-1)*2;
cout<<sum<<endl;

B.Kvass and the Fair Nut （二分)

题意

N个桶，需要K升酒，问取完K升酒后 桶中剩余酒的最小值的最大是多少

题解

直接二分答案，判断把酒取到这个值能否到达K升，注意如果本身就有酒比答案小的话直接返回false

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll a[maxn];
bool ok(int mid,int n,ll s){
    ll cnt=0;
    for(int i=1;i<=n;i++){
        cnt+=ll(max(0LL,a[i]-mid));
        if(a[i]<mid)return false;
    }
    if(cnt>=s)return true;
    else return false;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    ll s;
    cin>>n>>s;
    ll sum=0;
    ll mx=-inf;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=1LL*a[i],mx=max(a[i],mx);
    if(sum<s){cout<<-1<<endl;exit(0);}
    sort(a,a+n);
    int l=0,r=mx;
    int ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(ok(mid,n,s)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}

C.The Fair Nut and String (组合数学/DP)

题意

给你一个字符串，让你构造下标组成的严格递增序列

要求：1.这些下标对应字符串必须是‘a’

2.相邻两个下标之间必须在原字符串中隔着一个’b’

题解

把字符串分块，对于每个块中的a有块的大小种取法，但是也可以不取，所以对大小+1表示这个块都不取，然后根据乘法原理，相乘，最后因为题目要求不能有空的序列，所以答案-1；

1
2
3
4
5
6
7
8
9
10
11
12
string s;
cin>>s;
int len=s.length();
ll ans=1;
ll a=0;
for(int i=0;i<len;i++){
    if(s[i]=='a')a++;
    else if(s[i]=='b')ans=(ans*(a+1LL))%mod,a=0;
}
ans=(ans*(a+1LL))%mod;
ans--;ans+=mod;ans%=mod;
cout<<ans<<endl;

D.The Fair Nut and the Best Path (裸的树DP 维护最大次大值)

题意

每个点都有正权值，每条边都有负权值，选择一个边，使得经过的总权值最大

题解

对于每一个点，都有走一条边和走两条边两种选择，走一条边肯定是选择权值最大的，两条边就是权值第二大的加起来；

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll w[maxn];
struct node{
    int to;
    ll c;
};
vector<node>ve[maxn];
void add(int u,int v,ll c){
    ve[u].push_back(node{v,c});
    ve[v].push_back(node{u,c});
}
ll mx=-inf;
ll dp1[maxn],dp2[maxn];
void dfs(int now,int pre){
    dp1[now]=0;
    dp2[now]=0;
    ll ans1=0,ans2=0;
    for(auto i:ve[now]){
        int to=i.to;
        ll value=i.c;
        if(to==pre)continue;
        dfs(to,now);
        if(dp1[to]-value>ans1){
            ans2=ans1;
            ans1=dp1[to]-value;
        }
        else if(dp1[to]-value>ans2)ans2=dp1[to]-value;
    }
    dp1[now]=max(0LL,ans1+w[now]);
    dp2[now]=max(0LL,ans1+ans2+w[now]);
    mx=max(mx,max(dp1[now],dp2[now]));
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<n;i++){
        int u,v;ll c;
        cin>>u>>v>>c;
        add(u,v,c);
    }
    dfs(1,-1);
    cout<<mx<<endl;
    return 0;
}

E.The Fair Nut and Strings (01字典树)

题意

他写了K个字符串 ，字符串由a,b组成，c是这K个字符串的（不同前缀）的数目

他忘记了他的K个字符串，但是他还记得 这K个字符串的字典序最大T和字典序最小S 意思就是 这K个字符串最大的字符串是T最小的字符串是S

求构造K个字符串，求出这K个字符串的最大不同前缀数目；

题解

把a和b堪称0和1,然后组成一个0 1 字典树，

1.发现树的结点数就是答案；

2.k代表最多分出K个分支，

字符串T和S之间的间隔就是K个分支可以插的地方，

一个优化：如果第n层的分支数大于等于K那么肯定接下来的n+1层的结点数肯定可以有K个

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll n,k;
    cin>>n>>k;
    string s,t;
    cin>>s>>t;
    ll ans=0;
    ll a=0,b=0;
    for(int i=0;i<n;i++){
        a<<=1;b<<=1;
        a|=(s[i]-'a');b|=(t[i]-'a');
        if(b-a+1>=k){
            ans+=k*(n-i);break;
        }
        ans+=(b-a+1);
        if(b==a)b=a=0;
    }
    cout<<ans<<endl;
    return 0;
}

F.Max Mex ( )

题意

题解