Codeforces Round #543 (Div. 2, based on Technocup 2019 Final Round)

A. Technogoblet of Fire

题意：n个人分别属于m个不同的学校每个学校的最强者能够选中黑客要使 k个他选中的可以稳被选所以就为这k个人伪造学校问最小需要伪造多少个

思路：记录每个学校都有哪些人每次看黑客选中的人是不是在学校是最强者（这里要处理能力一样的情况，如果有能力一样的为了保证稳进也要伪造一个学校）然后就是模拟了

 1 #include<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 #define F first 
 5 #define S second
 6 #define pii pair<int ,int >
 7 #define mkp make_pair
 8 #define pb push_back
 9 using namespace std;
10 const int maxn=500+5;
11 vector<pii>v[maxn];
12 int p[maxn],s[maxn];
13 
14 int main(){
15     int n,m,k;
16     scanf("%d%d%d",&n,&m,&k);
17     FOR(i,1,n)scanf("%d",&p[i]);
18     FOR(i,1,n){
19         scanf("%d",&s[i]);
20         v[s[i]].pb(mkp(p[i],i));
21     }
22     int cnt=0;
23     int id;
24     FOR(i,0,k-1){
25         scanf("%d",&id);
26         for(int j=0;j<v[s[id]].size();j++){
27             if(v[s[id]][j].F>=p[id]&&v[s[id]][j].S!=id){
28                 cnt++;
29                 break;
30             }
31         }
32         for(int j=0;j<v[s[id]].size();j++){
33             if(v[s[id]][j]==mkp(p[id],s[id])){
34                 v[s[id]].erase(v[s[id]].begin()+j);
35                     break;
36             }    
37         }
38     }
39     cout<<cnt<<endl;
40     return 0;
41 }

View Code

B. Mike and Children

题意：给出N个数每个数都不一样两两组合问使组合后的和相等的最大对数是几

思路：因为每个数字都不一样直接暴力枚举每个可能的值即可

 1 #include<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 #define F first 
 5 #define S second
 6 #define pii pair<int ,int >
 7 #define mkp make_pair
 8 #define pb push_back
 9 using namespace std;
10 const int maxn=5000+5;
11 vector<pii>v[maxn];
12 int a[maxn],s[maxn];
13 set<int>q;
14 map<int,int>mp;
15 int main(){
16     int n;
17     scanf("%d",&n);
18     FOR(i,0,n-1){scanf("%d",&a[i]);}
19     int cnt=0;
20     int id=0;
21     FOR(i,0,n-1){
22         FOR(j,i+1,n-1){
23             q.insert(a[i]+a[j]);
24             mp[a[i]+a[j]]++;
25                 if(cnt<mp[a[i]+a[j]]){
26                     cnt=mp[a[i]+a[j]];
27                     id=a[i]+a[j];
28                 }
29         }
30     }
31     
32     cout<<cnt<<endl;
33 }

View Code

C. System Testing

题意：一秒测试一个样例一共有m台机器和n个题目给出每个题目的样例数问存在多少个round(100*ok/n) ==当前测试到的样例数 ok是已经完成的题数

思路：这里刚开始写的时候是用优先队列模拟的，会出现一个bug 因为是并行计算的，所以当前最先完成测试的题目测试到的样例满足round(100*ok/n)==样例数可能会出现在上上个题目之前（包含上上个）这样就会统计不到

所以还是离散化秒数用秒模拟即可（这题的数据范围是允许的）参考了超哥的代码

 1 #include<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 #define F first 
 5 #define S second
 6 #define pii pair<int ,int >
 7 #define mkp make_pair
 8 #define pb push_back
 9 using namespace std;
10 const int maxn=1000+5;
11 int vis[maxn],mk[maxn],p[maxn],a[maxn];
12 int ans=0;
13 double ti=0.5;
14 int main(){
15     int n,k,m;
16     scanf("%d%d",&n,&k);
17     m=0;
18     int tmp;
19     FOR(i,1,n){
20         scanf("%d",&a[i]);
21     }
22     k=min(n,k);
23     FOR(i,1,k)vis[i]=1;
24     for(;;ti+=1){
25         for(int i=1;i<=n;i++){
26             if(vis[i]==1)p[i]++;
27         }
28 
29     int d=round(100.0*m/n);
30 
31         for(int i=1;i<=n;i++){
32             if(vis[i]==1&&p[i]==d&&!mk[i]){ans++;mk[i]=1;}
33         }
34         
35         for(int i=1;i<=n;i++){
36             if(p[i]==a[i]&&vis[i]==1){
37                 m++;
38                 vis[i]=-1;
39                 for(int j=i+1;j<=n;j++){
40                     if(!vis[j]){vis[j]=1;break;}
41                 }
42             }
43         }
44         if(m==n)break;
45     }
46     cout<<ans<<endl;
47 return 0;
48 }

View Code

F. Compress String

把一个字符串包装成很多个连续的部分单个字符串需要消耗a 如果 tl tl+1 ...tr是前面t1...tl-1的子序列只需要消耗b问最小代价

思路：维护一个最长公共子串详细见代码

 1 #include<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 #define F first 
 5 #define S second
 6 #define pii pair<int ,int >
 7 #define mkp make_pair
 8 #define pb push_back
 9 using namespace std;
10 const int maxn=5000+5;
11 int dp[maxn];
12 int lcs[maxn][maxn];
13 char s[maxn];
14 int main(){
15     int n,a,b;
16     scanf("%d%d%d",&n,&a,&b);
17     scanf("%s",s+1);
18     FOR(i,1,n){
19         dp[i]=dp[i-1]+a;//初始化删一个
20         FOR(j,1,i-1){
21         if(s[i]==s[j])lcs[i][j]=lcs[i-1][j-1]+1;// 维护前i个和前j的最长公共子串并且终点是在i的
22         if(lcs[i][j]!=0&&i-j>=lcs[i][j])dp[i]=min(dp[i],dp[i-lcs[i][j]]+b);//如果1-i,1-j存在公共子串其中一个终点在i并且大区间（也就是终点的i）的起点在小区间的前面 即可更新dp[i][j] 可画图理解其正确性
23         }
24     }
25     cout<<dp[n]<<endl;
26     return 0;
27 }