Codeforces Round #788 (Div. 2)题解。

实况在这里

A. Prof. Slim

题目描述：

题目分析

给你一个序列，一次操作会使序列中的两个数交换符号但不交换大小，问能否在若干次操作后使得序列不递减。容易得到负数的个数一定不变并且负数永远小于正数，因此最后的结果一定是负数全在前面，正数全在后面，因为一个位置的数的绝对值一定不会改变，所以可以得到在绝对值中，负数区域一定不递增，正数区域一定不递减。先 O(n) 统计所有的负数的个数，再判断就ok了。

标程

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>
#define maxn 200005
#define maxx 40005
//#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");return;}
using namespace std;
char s[maxn];
int a[maxn],b[maxn]; 
int n,k;
void solve(){
    cin>>n;
    int num_de=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]<0){
            num_de++;
        }
    }
    for(int i=2;i<=num_de;i++){
        if(abs(a[i])-abs(a[i-1])>0)NO
    }
    for(int i=num_de+2;i<=n;i++){
        if(abs(a[i])-abs(a[i-1])<0)NO
    }
    OK
    
    
}
void init(){
    
} 
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    init();
    while(t--)solve();
    
    return 0;
}

B. Dorms War

题目描述：

题目分析

这题目题意分析了很久，后面看了很久才看出来。就是说给你一个字符串和若干个特殊字符，每次操作会使得特殊字符前面的那个字符消失，直到字符不会再消失为止，问你一共消失几次，特殊字符可以被前面的特殊字符消除。

其实不难发现，一个特殊字符吞前面字符的次数就相当于它距离最近的一个特殊字符的距离+1。多个特殊字符不影响结果，取最大即可，明明是 O(n) 的算法，写的时间却很高，甚至因此 T 了一次。以后一定要记得 IO 优化，拒绝 cin，从我做起。

标程

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
#include<bits/stdc++.h>
#define maxn 200005
#define maxx 40005
//#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");return;}
using namespace std;
char s[maxn];
int a[maxn],b[maxn]; 
int spec[100];
int n,k;
void solve(){
    scanf("%d",&n);
    scanf("%s",s);
    scanf("%d",&k);
    memset(spec,0,sizeof(spec));
    string tmp;
    for(int i=1;i<=k;i++){
        cin>>tmp;
        spec[tmp[0]-'a']=1;
    }
    int cnt=0;
    int ans=0;
    for(int i=0;i<n;i++){
        if(spec[s[i]-'a']){
            ans=max(ans,cnt);
            cnt=0;
        }
        cnt++;
    }
    
    printf("%d\n",ans);
}
void init(){
    
} 
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    init();
    while(t--)solve();
    
    
    
    return 0;
}

C. Where is the Pizza?

题目描述

题目分析

选择其中一个数导致了另一个必然不选，所以这里又要选另一个必选的数，然后对于每个环只有两种方案，找到环个数相乘a和b用散列保存位置。b数组全部指向a。a数组指向 自己那个值在 b 中的位置。每次判断 这个环中的位置对应的 c是否全为0。最后特判两个相等的时候这个情况也不 乘2。

标程

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
#include<bits/stdc++.h>
#define maxn 100005
#define maxx 40005
//#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");return;}
using namespace std;
char s[maxn];
int a[maxn],b[maxn],a_[maxn],b_[maxn],c[maxn],vis[maxn]; 
int spec[100];
int n,k;
const int mod=1e9+7;
queue<int>q;
int dfs(int pos){
    int flag=1;
    q.push(pos);
    while(q.size()){
        int x=q.front();
        q.pop();
        if(!vis[x]){
            vis[x]=1;
            q.push(b_[a[x]]);
            q.push(a_[b[x]]);
        }
        if(c[x]){
            flag=0;
        }
        if(a[x]==b[x]){
            flag=0;
        }
    }
    return flag;
    
}
void solve(){
    int n;
    cin>>n;
    long long ans=1;
    memset(vis,0,sizeof(int)*(n+1));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a_[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        b_[b[i]]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>c[i];    
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            int res=dfs(i);
            if(res){
                ans*=2;
                ans%=mod;
            }
        }
    }
    printf("%lld\n",ans);
    
}
void init(){
    
} 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    init();
    while(t--)solve();
    
    
    
    return 0;
}

D. Very Suspicious

题目描述

题目分析

计算几何，自己画一下会发现：三线相交得到6个，两线相交得到2个，线只有三种方向。每添加一条线凑成三线相交，方案数+4，与其它不平行的线相交，每多一个方案数+2。然后打一遍表，把 1e9 以内的答案跑出来最后二分寻找答案即可。

标程

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
#include<bits/stdc++.h>
#define maxn 100005
#define maxx 40005
//#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");return;}
using namespace std;
char s[maxn];
int a[maxn],b[maxn],a_[maxn],b_[maxn],c[maxn],vis[maxn]; 
int ans[maxn];
void solve(){
    int n;
    cin>>n;
    int d=lower_bound(ans,ans+maxn,n)-ans;
    printf("%d\n",d);
}
void init(){
    int num[3]={2,1,1};
    memset(ans,0x3f,sizeof(ans));
    ans[0]=0;
    ans[1]=0;
    ans[2]=2;
    ans[3]=6;
    ans[4]=10;
    int cnt=10;
    int i=4;
    for(;cnt<=1e9;i++){
        int sel=i%3;
        cnt+=(num[(sel+1)%3]+num[(sel+2)%3]-2)*2;
        cnt+=4;
        num[sel]++;
        ans[i+1]=cnt;
    }
} 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    init();
    while(t--)solve();
    
    
    
    return 0;
}

这波也是上大分，上了38分，希望再接再厉，争取快点上紫。