本文共 6022 字，大约阅读时间需要 20 分钟。
（找规律）
题意：给定n，要求把[1,n]分成两个集合，使得两个集合的元素和之差最小，问最小值是多少。
（1<=n<=2e9）思路：看到n的范围大概就猜想这题是找规律题，
我们令sum为[1,n]的元素和，d为最小差值 n=1,sum=1 ，d=1n=2,sum=3， d=1
n=3,sum=6， d=0
n=4 ,sum=10，d=0
n=5,num=15 ，d=1
n=6,num=21, d=1
n=7,num=28, d=0
可以看出，如果sum是偶数，那么d一定是0，否则是1
#include#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define Please return#define AC 0;#define LL long long #define ULL unsigned long long const LL INF=2e18+7;const int maxn=2e9+7;const int mod=1e9;int n,m;LL sum;int main(){ scanf("%d",&n); sum=(n+1)*n/2; if(sum&1) cout<<1; else cout<<0; Please AC}
（贪心）
题意：给定一个长度为n的数组，用k种颜色给每个元素上色，
规定是颜色必须用完，每个元素必须涂色，元素值相同的元素不能涂同一种颜色， 输出任意一种涂法，不能按要求涂的话输出NO （1<=n,k<=3e3）思路：先特判不能涂的情况，1、最大元素相等集的个数大于k，也就是颜色种类过少
2、元素个数小于k，也就是颜色种类过多剩下的情况就一定可以涂，先把k个颜色都用一遍，用cnt[i][j]记录对于值为i的元素，j号颜色是否涂过
#include#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define Please return#define AC 0;#define LL long long #define ULL unsigned long long const LL INF=2e18+7;const int maxn=5e3+7;const int mod=1e9;int n,k,a[maxn];int book[maxn];bool cnt[maxn][maxn];//每个元素都上色，每个颜色都要用，相同值的数组元素不能上同一种色struct node{ int v,num; friend bool operator<(const node &a,const node &b) { return a.num>b.num; }};vector an;int main(){ scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",a+i); book[a[i]]++; } for(int i=1;i<=maxn;i++) { if(book[i]) { an.push_back({ i,book[i]}); } } sort(an.begin(),an.end()); if(an.begin()->num>k || n
（思维）
题意：给定一个长度为n的数组，给定x，y，甲每轮可以让一个非0数减少x，如果减少成了负数就取为0，乙每轮让一个非0数增加y，甲先开始，甲乙两人都采取最优策略，问无数轮之后元素中有几个0
1<=n<=100
思路：x>y, n个都会变成0
x<=y,答案为 原始数组中小于等于x的元素的一半，如果是奇数再加1
#includeusing namespace std;#define Please return#define AC 0;#define LL long long #define ULL unsigned long long const LL INF=2e18+7;const int maxn=3e5+7;const int mod=1e9;int n,x,y;int a[105];int main(){ scanf("%d %d %d",&n,&x,&y); for(int i=1;i<=n;i++) scanf("%d",a+i); if(x>y) { printf("%d\n",n); } else { int tot=0; for(int i=1;i<=n;i++) { if(a[i]<=x) tot++; } cout<<(tot+1)/2<<'\n'; } Please AC}
（思维+贪心）
题目大意：给定0 1 2组成的长度为n的字符串，每次可以选择把1个字符替换成别的，问如何替换最少位置的字符，使得字符串0 1 2的个数相等，且字符串的字典序最小。 输出替换后的字符串。
（3<=n<=3e5）思路：这题要求的是改变最少位置的字符，并没有限制改变的次数 ，所以可以同一个位置改多次 。
我们就先记录原串中0 1 2的个数，
然后如果2多了 ，就从前面开始遍历，优先把2改成0 ，0够了再改成1
如果1多了，先从前面开始遍历把1改成0，直到0够了，再从后往前遍历把1改成2，直到2够了
如果0多了，从后面往前遍历，优先改成2，2够了再改成1
#includeusing namespace std;#define Please return#define AC 0;#define LL long long #define ULL unsigned long long const LL INF=2e18+7;const int maxn=3e5+7;const int mod=1e9;int len;char s[maxn];int num[128];int main(){ scanf("%d%s",&len,s+1); for(int i=1;i<=len;i++) { num[s[i]]++; } num['0']-=len/3; num['1']-=len/3; num['2']-=len/3; if(num['2']>0)//从前往后 优先换成0 { for(int i=1;i<=len && num['2']>0;i++) { if(s[i]=='2') { if(num['0']<0) { s[i]='0'; num['0']++; num['2']--; } else if(num['1']<0) { s[i]='1'; num['1']++; num['2']--; } } } } if(num['1']>0)//先从前往后换0，再从后往前换2 { for(int i=1;i<=len && num['1']>0 && num['0']<0;i++) { if(s[i]=='1') { s[i]='0'; num['0']++; num['1']--; } } for(int i=len;i>=1 && num['1']>0 && num['2']<0;i--) { if(s[i]=='1') { s[i]='2'; num['2']++; num['1']--; } } } if(num['0']>0)//从后往前先换2 再换1 { for(int i=len;i>=1 &&num['0']>0;i--) { if(s[i]=='0') { if(num['2']<0) { s[i]='2'; num['2']++; num['0']--; } else if(num['1']<0) { s[i]='1'; num['1']++; num['0']--; } } } } cout<
（状压dp+预处理思维）
题意：给定一个矩阵，最多16行1000列，可以把各行按任意顺序换置，最终使得k最大。
k的计算方法为：矩阵从左上角往下遍历，计算当前元素和下一个遍历元素的差值，（遍历到这列末尾后就换到右列的第一个元素，直到遍历完右下角） 。
k就是这些差值中的最小值。思路：行数只有16行，我们考虑从首行开始dfs枚举， dp[1<<16][20][20]用于记忆化搜索 ，dp[sta][i][j]表示当前枚举状态为sta,首行为第i行，目前枚举的最后一行的第j行
所以我们先预处理得到任意两行之间，对应位置相差值的最小值
再预处理，任意两行作为首末行时，对应位置相差值的最小值