2021ICPC四川省赛个人补题ABDHKLM

Dashboard - The 2021 Sichuan Provincial Collegiate Programming Contest - Codeforces

过题难度：

A K D M H B L

铜奖 5  594

银奖 6 368

金奖 8 755

codeforces.com/gym/103117/problem/A

模拟出牌的过程，打表即可

// Code Start Here	int t;cin >> t;while(t--){int n;cin >> n;if(n == 1)cout << 0 << endl;else if(n == 2) cout << 1 <<endl;else if(n == 3)cout << 1 <<endl;else if(n == 4)cout << 2 <<endl;else if(n == 5)cout << 2 <<endl;else if(n == 6)cout << 3 <<endl;else if(n == 7)cout << 3 <<endl;else if(n == 8)cout << 3 <<endl;else if(n == 9)cout << 2 <<endl;else if(n == 10)cout << 2 <<endl;else if(n == 11)cout << 1 <<endl;else if(n == 12)cout << 1 <<endl;else cout << 0 << endl;}

Problem - K - Codeforces

我们发现最优解肯定是间隔是K的尽量在一起，模拟即可

int n , k;cin >> n >> k;if(k >= n){for(int i = 1;i<n;i++)cout << i << " ";cout << n << endl;}else{vector<bool> vis(n + 1, false);vector<int> ans;for(int i = 1;i<=n;i++){if(!vis[i]){vis[i] = true;for(int j = i;j<=n;j += k){ans.push_back(j);vis[j] = true;}}}for(int i = 0;i<(int)(ans.size())-1;i++){cout << ans[i] << " ";	}cout << ans.back() << endl;}

Problem - D - Codeforces

模拟剪刀石头布即可

int a1,b1,c1,a2,b2,c2;cin>>a1>>b1>>c1>>a2>>b2>>c2;int sum=0;int min1=min(a1,b2);sum+=min1;a1-=min1;b2-=min1;min1=min(b1,c2);sum+=min1;b1-=min1;c2-=min1;min1=min(c1,a2);sum+=min1;c1-=min1;a2-=min1;min1=min(a1,a2);a2-=min1;min1=min(b1,b2);b2-=min1;min1=min(c1,c2);c2-=min1;int p=0;p=max(a2,b2);p=max(p,c2);sum-=p;cout<<sum<<endl;

codeforces.com/gym/103117/problem/M

我们考虑整个扩张的过程，在0 ~ p0内的扩张肯定优先走0~p0，而在0~p0外的扩张对于1e5 * 1e5不现实，考虑优化，只保留一个最大的区间，如果这个区间可以通过，那么一定存在答案

int n , k , x , p0;cin >> n >> k >> x >> p0;vector<int> v(n + 1);for(int i = 1;i<=n;i++)cin >> v[i];vector<int> l(k+1),r(k+1);for(int i = 1;i<=k;i++)cin >> l[i];for(int i = 1;i<=k;i++)cin >> r[i];int max_val = -1;for(int i = 1;i<=k;i++){if(l[i] >= p0){max_val = max(max_val , r[i] - l[i]);}}int max_time = max(p0 , max_val);int ans = 0;for(int i = 1;i<=n;i++){if(v[i] * max_time >= x)ans++;}cout << ans << endl;

codeforces.com/gym/103117/problem/H

大模拟

string s;cin >> s;string now = "";// 构造 imasuif(!s.empty()) now += s.back() , s.pop_back();if(!s.empty()) now += s.back() , s.pop_back();if(!s.empty()) now += s.back() , s.pop_back();if(!s.empty()) now += s.back() , s.pop_back();if(!s.empty()) now += s.back() , s.pop_back();reverse(now.begin(),now.end());if(now != "imasu")cout << s << now << endl;else{char ch2 , ch1;if(!s.empty())ch2 = s.back() , s.pop_back();if(!s.empty())ch1 = s.back() , s.pop_back();if(ch1 == 'c' && ch2 == 'h'){cout << s << "tte" << endl;return;}if(ch1 == 's' && ch2 == 'h'){cout << s << "shite" << endl;return;}if(ch1 == 'i' && ch2 == 'k' && s.empty()){cout << s  << "itte" << endl;return;}if(ch1 == 'i' && ch2 == 'k' && !s.empty()){cout << s  << "iite" << endl;return;}if(ch2 == 'r'){cout << s << ch1 << "tte" << endl;return ;}if(ch2 == 'm' || ch2 == 'b' || ch2 == 'n'){cout << s << ch1 << "nde" << endl;return;}if(ch2 == 'k'){cout << s << ch1 << "ite" << endl;return;}if(ch2 == 'g'){cout << s << ch1 << "ide" << endl;return;}cout << s << ch1 << ch2 << now << endl;

Problem - B - Codeforces

考虑从奇偶性入手来找回合数，特别要注意的是如果一开始为0的话那么后面无法进行，需要特判

	int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>a[i];}int sum1=k/n;int sum2=k%n;vector<int>pre(m+1),last(m+1);map<int,int>p;vector<int>sum(n+1);
//	cout<<sum1<<endl;if(sum1==0){map<int,int>p3;for(int i=1;i<=sum2;i++){if(p3[a[i]]){sum[i]++;p3[a[i]]--;continue;}p3[a[i]]++;}for(int i=1;i<n;i++){cout<<sum[i]<<' ';}cout<<sum[n]<<endl;return ;}for(int i=1;i<=n;i++){p[a[i]]++;if(p[a[i]]==1){pre[a[i]]=i;}last[a[i]]=i;}map<int,int>p4;for(int i=1;i<=n;i++){p4[a[i]]++;if(p[a[i]]%2==0){if(p4[a[i]]%2==0){sum[i]+=sum1;}}else{if(p[a[i]]==1){sum[i]+=sum1/2;}else{if(sum1&1){if(p4[a[i]]&1){sum[i]+=sum1/2;}else{sum[i]+=sum1/2+1;}}else{sum[i]+=sum1/2;}}}}map<int,int>p2;for(int i=1;i<=sum2;i++){p2[a[i]]++;if(p[a[i]]==1){if(sum1%2==0){continue;}else{sum[i]++;continue;}}if(p[a[i]]%2==1){if(sum1&1){if(p2[a[i]]%2==1){sum[i]++;continue;}else{continue;}}else{if(p2[a[i]]%2==0){sum[i]++;}continue;}}if(p2[a[i]]%2==0){sum[i]++;continue;}}for(int i=1;i<n;i++){cout<<sum[i]<<' ';}cout<<sum[n];cout<<endl;

https://codeforces.com/gym/103117/problem/L

按照权值分类，跑 100 次bfs，将题目给出的终点作为起点，将所有其他所有点作为终点。在符合条件的权值下找到最小值

vector<int>g[N];
vector<int>val[110];
int ans[110][N];
int vis[N];void bfs(int n){queue<pair<int, int>>q;for(int i=0; i<val[n].size(); i++){vis[val[n][i]] = 1;q.push(make_pair(val[n][i], 0));}while(q.size()){pair<int,int> x = q.front();q.pop();int now = x.first;ans[n][now] = x.second;for(int i=0; i<g[now].size(); i++){int nxt = g[now][i];if(vis[nxt]) continue;vis[nxt] = 1;q.push({nxt, x.second + 1});}}
}int32_t main(){int n, m, q, w = 0;cin >> n >> m >> q;for(int i=1; i<=n; i++){int a;cin >> a;w = max(a , w);val[a].push_back(i);}for(int i=0; i<m; i++){int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);}for(int i=0; i<=w; i++) for(int j=0; j<=n; j++) ans[i][j] = n;for(int i=1; i<=w; i++){for(int j=0; j<=n; j++) vis[j] = 0;bfs(i);}while(q--){int a, b;cin >> a >> b;int x = n;for(int i=1; i<=b; i++) x = ans[i][a] < x ? ans[i][a] : x;if(x == n)cout << -1 << endl;else cout << x << endl;}return 0;
}