签到，思维拓展
You are given an integer sequence 1,2,…,n1,2,…,n. You have to divide it into two sets AAand BB in such a way that each element belongs to exactly one set and |sum(A)−sum(B)||sum(A)−sum(B)| is minimum possible.
The value |x||x| is the absolute value of xx and sum(S)sum(S) is the sum of elements of the set SS.
Input
The first line of the input contains one integer nn (1≤n≤2⋅1091≤n≤2⋅109).
Output
Print one integer — the minimum possible value of |sum(A)−sum(B)||sum(A)−sum(B)| if you divide the initial sequence 1,2,…,n1,2,…,n into two sets AA and BB.
题意：给你一个n，即1-n的一个序列，问你能否将数列中的数分成两个子序列 且满足两个子序列的和之差的绝对值最小，输出这个差的绝对值。
思路：首先对这个序列求和，如果和是奇数，就输出1，否则输出0.
然后我们对这个问题进行下简单拓展，如果这个序列不是满足1-n，而是直接给你n个数呢。
这里我们也是相似的做法，我们先对这个序列求和，然后通过不断加数进一个序列，使得这个序列不断逼近和的一半，而直到当加了一个数的时候，这个序列的和超过了总和的一半，这时就只需要判断是否要加这个数，两种情况的值，选最小即可。
本题的代码：(这里还需要注意会爆int）
#include <bits/stdc++.h> using namespace std; int main() { long long n; cin>>n; long long ans=(n+1)*n/2; if(ans%2==1) cout<<1<<endl; else cout<<0<<endl; return 0; }
You are given an array aa consisting of nn integer numbers.
You have to color this array in kk colors in such a way that:
- Each element of the array should be colored in some color;
- For each ii from 11 to kk there should be at least one element colored in the ii-th color in the array;
- For each ii from 11 to kk all elements colored in the ii-th color should be distinct.
Obviously, such coloring might be impossible. In this case, print "NO". Otherwise print "YES" and any coloring (i.e. numbers c1,c2,…cnc1,c2,…cn, where 1≤ci≤k1≤ci≤k and cici is the color of the ii-th element of the given array) satisfying the conditions above. If there are multiple answers, you can print any.
Input
The first line of the input contains two integers nn and kk (1≤k≤n≤50001≤k≤n≤5000) — the length of the array aa and the number of colors, respectively.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤50001≤ai≤5000) — elements of the array aa.
Output
If there is no answer, print "NO". Otherwise print "YES" and any coloring (i.e. numbers c1,c2,…cnc1,c2,…cn, where 1≤ci≤k1≤ci≤k and cici is the color of the ii-th element of the given array) satisfying the conditions described in the problem statement. If there are multiple answers, you can print any.
题意：首先给你n个数的一个序列，以及k种颜色，你需要做到序列中的每个数都必须染色，且每种颜色都必须用到，而且每种颜色所涂的数中不能有相同的数。如果能做到，输出这个序列的涂色方案（不唯一）
思路：首先我们判断是否能够涂成功。我们计算这个序列中相同的数出现的最大次数。如果这个最大次数大于k，则失败，否则成功。
对于成功的，我们需要求出方案。我的方法比较复杂，想的有点多。我先统计了每个数的出现次数，然后我们遍历这个序列，每个数的颜色就是他们出现的次数，然后出现次数减一。这里就满足每种颜色所涂的数中没有相同的数，但是没要保证每种颜色都出现。这时我们对于这个方案进行改善。我们需要将出现多次的颜色向后推，推到没有出现的颜色，然后将这个颜色改掉，即满足出现每种颜色。
#include <bits/stdc++.h> using namespace std; int main() { int n,m; cin>>n>>m; int num[5005]; memset(num,0,sizeof(num)); int a[5005]; int maps[5005]; int k[5005]; map<int,int>ss; memset(maps,0,sizeof(maps)); for(int i=0;i<n;i++){ cin>>a[i]; num[a[i]]++; } int maxx=-1; for(int i=0;i<=5000;i++) maxx=max(maxx,num[i]); if(maxx>m) cout<<"NO"<<endl; else{ cout<<"YES"<<endl; for(int i=0;i<n;i++){ k[i]=num[a[i]]; num[a[i]]--; } for(int i=0;i<n;i++){ if(!ss[k[i]]) ss[k[i]]++; else { int t=k[i]+1; while(t<=m){ if(!ss[t]){ k[i]=t; ss[t]++; break; } t++; } } } for(int i=0;i<n;i++) cout<<k[i]<<' '; } return 0; }
C - Doors Breaking and Repairing
You are policeman and you are playing a game with Slavik. The game is turn-based and each turn consists of two phases. During the first phase you make your move and during the second phase Slavik makes his move.
There are nn doors, the ii-th door initially has durability equal to aiai.
During your move you can try to break one of the doors. If you choose door ii and its current durability is bibi then you reduce its durability to max(0,bi−x)max(0,bi−x) (the value xxis given).
During Slavik's move he tries to repair one of the doors. If he chooses door ii and its current durability is bibi then he increases its durability to bi+ybi+y (the value yyis given). Slavik cannot repair doors with current durability equal to 00.
The game lasts 1010010100 turns. If some player cannot make his move then he has to skip it.
Your goal is to maximize the number of doors with durability equal to 00 at the end of the game. You can assume that Slavik wants to minimize the number of such doors. What is the number of such doors in the end if you both play optimally?
Input
The first line of the input contains three integers nn, xx and yy (1≤n≤1001≤n≤100, 1≤x,y≤1051≤x,y≤105) — the number of doors, value xx and value yy, respectively.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1051≤ai≤105), where aiaiis the initial durability of the ii-th door.
Output
Print one integer — the number of doors with durability equal to 00 at the end of the game, if you and Slavik both play optimally.
题意：别看题目这么长，其实有用的就几句话，首先给你n个数的一个序列，以及a和b，a表示每次可以使序列中的一个数减去a（直到为0），b表示每次对序列中的一个非零数加上b，按顺序减加减加循环下去。然后问序列中有多少为零的数。
思路：一开始想的是博弈。但是其实并没有这么复杂，只需要分两种情况。一种数a大于b，必定会使得所有数都变成0，即输出n。一种数a小于b，这时我们再输入的时候记录下这个序列中小于等于a的数的个数ans，如果这个序列中大于a的数，是不可能被减为0的。然后对于小于等于a的数，我们就根据循环，当是减的时候，这个数就变成0了，当是加的时候，这个数就大于a了，即不可能减为0.这里就是ans/2，对于ans是奇数，则因为先手是减，所以奇数加一。
#include <bits/stdc++.h> using namespace std; int main() { int n,a,b,c; int num[105]; int t=0; cin>>n>>a>>b; int ans=0; for(int i=0;i<n;i++){ cin>>c; if(c<=a) ans++; else num[t++]=c; } if(a>b) cout<<n<<endl; else{ if(ans%2==1) ans++; cout<<ans/2<<endl; } return 0; }
You are given a string ss consisting of exactly nn characters, and each character is either '0', '1' or '2'. Such strings are called ternary strings.
Your task is to replace minimum number of characters in this string with other characters to obtain a balanced ternary string (balanced ternary string is a ternary string such that the number of characters '0' in this string is equal to the number of characters '1', and the number of characters '1' (and '0' obviously) is equal to the number of characters '2').
Among all possible balanced ternary strings you have to obtain the lexicographically (alphabetically) smallest.
Note that you can neither remove characters from the string nor add characters to the string. Also note that you can replace the given characters only with characters '0', '1' and '2'.
It is guaranteed that the answer exists.
Input
The first line of the input contains one integer nn (3≤n≤3⋅1053≤n≤3⋅105, nn is divisible by 33) — the number of characters in ss.
The second line contains the string ss consisting of exactly nn characters '0', '1' and '2'.
Output
Print one string — the lexicographically (alphabetically) smallest balanced ternary string which can be obtained from the given one with minimum number of replacements.
Because nn is divisible by 33 it is obvious that the answer exists. And it is obvious that there is only one possible answer.
题意：给你一串长度是3的倍数的‘0’ ‘1’ ‘2’组成的串，问在最小操作的情况下，使得三个字符个数相等的最小串。（操作是指转换）
思路：自闭了好久的一题。我们先找到什么时候满足最小操作。
首先是应该找到最少的那个字符，然后将最多的字符转换成那个最少的字符，这个循环去做。但是如果直接找的话有6个循环的全排列条件判断。这里不太好判断。
所以我们应该先统计每个字符出现的次数，出现的次数减去n/3，这里就表示需要或者多了多少个字符。然后先从前向后循环遍历，如果遍历到‘2’，且‘2’的出现次数大于0，我们优先判断‘0’，如果‘0’的出现次数小于0，则转换这个位置，否则在转换成‘1’。然后遍历到‘1’，如果‘1’的次数大于0，则判断‘0’的出现次数是否小于0，是则转换。
最后还需要逆着走一遍循环。如果遍历到‘0’且‘0’的次数大于0，则优先判断‘2’，如果‘2’的次数小于0，则转换，否则转换成‘1’，然后遍历‘1’，如果‘1’的次数大于.0，这判断‘2’的出现次数是否大于0，是则转换。
在转换的时候注意将出现次数进行修改。循环遍历两次也保证了最小串的生成。
#include <bits/stdc++.h> using namespace std; int main() { int n,m; string s; cin>>n; cin>>s; map<char,int> num; for(int i=0; i<s.length(); i++) { num[s[i]]++; } int a=num['0']-n/3; int b=num['1']-n/3; int c=num['2']-n/3; for(int i=0;i<n;i++){ if(s[i]=='2'&&c>0){ if(a<0){ a++; c--; s[i]='0'; } else if(b<0){ b++; c--; s[i]='1'; } } if(s[i]=='1'&&b>0){ if(a<0){ b--; a++; s[i]='0'; } } } for(int i=n-1;i>=0;i--){ if(s[i]=='0'&&a>0){ if(c<0){ c++; a--; s[i]='2'; } else if(b<0){ b++; a--; s[i]='1'; } } if(s[i]=='1'&&b>0){ if(c<0){ c++; b--; s[i]='2'; } } } cout<<s<<endl; return 0; }
京公网安备 11010502036488号