补题。最近状态很差，等着打校赛。
A - Array with Odd Sum
对(n)进行分类讨论：
(n)为奇数时，只要存在奇数即可；若(n)为偶数，必须同时包含奇数和偶数才能满足条件。
/* Author: EndlessK * Time: 2021-05-13 15:12:41 **/ #include<bits/stdc++.h> #define maxn 100010 #define pb push_back #define ll long long #define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; int num[2]={0}; int main() { fast; int t; cin>>t; while(t--) { num[0]=0; num[1]=0; int n; cin>>n; int x; for(int i=1;i<=n;i++) { cin>>x; num[x%2]++; } if(n%2) { if(num[1]) cout<<"YES "; else cout<<"NO "; } else { if(num[1] && num[0]) cout<<"YES "; else cout<<"NO "; } } return 0; }
B - Food Buying
题目概述：花费10个点数可获得一个点数，问最多花费多少个点数。
感觉没什么好说的，模拟就行了，直接上代码。
比A简单。
/* Author: EndlessK * Time: 2021-05-13 15:12:41 **/ #include<bits/stdc++.h> #define maxn 100010 #define pb push_back #define ll long long #define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; int main() { fast; int t; cin>>t; while(t--) { int x; cin>>x; int ans=x; while(x>=10) { ans+=x/10; x=x%10+x/10; } cout<<ans<<' '; } return 0; }
C - Yet Another Walking Robot
题目概述：对于原路径，删除尽可能短的子段使得机器人根据指令所到达的终点不变。
我们就假设起点为(0,0)，也是整个路径的第一个点。然后根据指令记录路径，并记录当前位置为路径的第几个点。如果已经记录，两值相减-1即为子串长度。（-1也可以不考虑，反正大家都一样）
如果得到的长度更短，就更新答案(l)和(r)。
/* Author: EndlessK * Time: 2021-05-13 15:12:41 **/ #include<bits/stdc++.h> #define maxn 100010 #define pb push_back #define ll long long #define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; int main() { fast; int t; cin>>t; map<pair<int,int>,int> mp; while(t--) { mp.clear(); int ansl=-1; int ansr=-1; int anslen=1e9; int n; cin>>n; string s; cin>>s; mp[make_pair(0,0)]=1; int x=0,y=0; for(int i=0;i<n;i++) { if(s[i]=='L') x--; if(s[i]=='R') x++; if(s[i]=='U') y++; if(s[i]=='D') y--; if(mp[make_pair(x,y)]) { if(i+2-mp[make_pair(x,y)]<anslen) { anslen=i+2-mp[make_pair(x,y)]; ansl=mp[make_pair(x,y)]; ansr=i+1; } mp[make_pair(x,y)]=i+2; } else mp[make_pair(x,y)]=i+2; } if(ansl==-1) cout<<"-1 "; else cout<<ansl<<' '<<ansr<<' '; } return 0; }
D - Fight with Monsters
题目概述：你和你的对手一起轮流打怪，你单次造成的伤害为(a)，对手单次造成的伤害为(b)，每次都是你先手。
1. 在你造成伤害后，如果这只怪物死亡，你获得1分，并且移步至下一只怪。
2. 在你的对手造成伤害后，如果这只怪物死亡，没人能获得分数，并且移步至下一只怪。
你有(k)次跳过对手回合的机会，问最多能获得多少分。
若(h[i]\%(a+b)<=a)且不为0，那么无需使用跳过机会就可以拿到这一分。
若(h[i]\%(a+b)>a)或者(h[i]\%(a+b)==0)，那么就需要考虑跳过对手回合了。我们记余数为(mod)，若想拿到这一分，就需要跳过(mod/a+(mod\%a==0))次，这个推导起来不难。记得原本余数为零的话就视为余数为(a+b)。
然后将所有的跳过次数进行排序，从小到大取，直到次数用完。
/* Author: EndlessK * Time: 2021-05-13 15:12:41 **/ #include<bits/stdc++.h> #define pb push_back #define ll long long #define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; const int maxn = 200010; int n,a,b,k; int h[maxn]; vector<int> v; int main() { fast; cin>>n>>a>>b>>k; for(int i=1;i<=n;i++) { cin>>h[i]; } sort(h+1,h+n+1); int ans=0; for(int i=1;i<=n;i++) { if(h[i]<=a) ans++; else { if(h[i]%(a+b)<=a && h[i]%(a+b)!=0) ans++; else { int tmp=h[i]%(a+b); if(tmp==0) tmp=a+b; v.pb(tmp/a-(tmp%a==0)); } } } sort(v.begin(),v.end()); // for(int i=0;i<v.size();i++) // { // cout<<v[i]<<' '; // } // cout<<' '; for(int i=0;i<v.size();i++) { if(v[i]<=k) { k-=v[i]; ans++; } } cout<<ans<<' '; return 0; }
E - String Coloring
题目概述：给所有的字母涂上颜色，如果相邻字母颜色不同即可进行交换，问最少需要几种颜色使得这些字母进行交换后非递减。
Easy version问的则是两种颜色是否满足。
本来考虑的是逆序对，后来发现同种颜色的序列满足非递减，那么就是要求序列中上升子序列的个数的最小值。
规律：下降子序列的个数等于最长上升子序列的长度，上升子序列的个数等于最长下降子序列的长度。
这个证明起来不难，因为昆明现场就发现了这一点。
而昆明的签到需要(nlogn)复杂度的LIS，但这题不需要，一共就26个字母。
对于每个字母，枚举比它大的字母，求得下降子序列长度的最大值(dp[i])。
整个序列的长度最大值即为颜色数量，(dp[i])即为每个字母对应的颜色。
E1:
/* Author: EndlessK * Time: 2021-05-13 15:12:41 **/ #include <bits/stdc++.h> #define pb push_back #define ll long long #define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) using namespace std; const int maxn = 210; int ans[maxn]; int dp[maxn]; vector<char> v[2]; int main() { fast; int n; cin >> n; string s; cin >> s; for (int i = 0; i < n; i++) { dp[i] = 1; } for (int i = 0; i < n; i++) { for (int j = 25; j > s[i] - 'a'; j--) { dp[i] = max(dp[i], ans[j] + 1); } ans[s[i] - 'a'] = max(ans[s[i] - 'a'], dp[i]); } int maxx = 0; for (int i = 0; i < 26; i++) { maxx = max(ans[i], maxx); } if (maxx <= 2) { cout << "YES "; for (int i = 0; i < n; i++) { cout << dp[i] - 1; } cout << ' '; } else { cout << "NO "; } return 0; }
E2:
/* Author: EndlessK * Time: 2021-05-13 15:12:41 **/ #include <bits/stdc++.h> #define pb push_back #define ll long long #define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) using namespace std; const int maxn = 200010; int ans[maxn]; int dp[maxn]; vector<char> v[2]; int main() { fast; int n; cin >> n; string s; cin >> s; for (int i = 0; i < n; i++) { dp[i] = 1; } for (int i = 0; i < n; i++) { for (int j = 25; j > s[i] - 'a'; j--) { dp[i] = max(dp[i], ans[j] + 1); } ans[s[i] - 'a'] = max(ans[s[i] - 'a'], dp[i]); } int maxx = 0; for (int i = 0; i < 26; i++) { maxx = max(ans[i], maxx); } cout << maxx << ' '; for (int i = 0; i < n; i++) { cout << dp[i] << ' '; } cout << ' '; return 0; }