本文共 6070 字，大约阅读时间需要 20 分钟。

纪录思维题

题意：利用 1 --> n 之间的数，构造 k 个peak，就是 ai > ai-1 && ai > ai+1(i 是下标)。 贪心。 首先发现 最多构造 (n-1)/2个，第一个放 1，后边的放一个 3 和一个 2，以此往后。模拟一下构造 k 个即可

#include
   
    typedef long long ll;using namespace std;const int N = 1e3 + 9;int n, k;ll a[N];vector 
    
      v;int main(){   	int t;	cin >> t;	while(t--)	{   		cin >> n >> k;		if(!k)		{   			for(int i = 1; i <= n; ++i)			{   				if(i>1) cout << " ";cout << i;			}cout << endl;		}		else if(n < 3 || k > (n-1)/2) printf("-1\n");		else		{   			v.push_back(1);			int cnt = 0;			int i = 2;			for(; i <= n; i += 2)			{   				if(i+1<=n) v.push_back(i+1);				++cnt;					v.push_back(i);				if(cnt == k) break;			}			for(int j = i + 2; j <= n; ++j) v.push_back(j);			for(int i = 0; i < v.size(); ++i)			{   				if(i > 0) cout << " ";				cout << v[i];			}			v.clear();			cout << endl;		}	}	return 0;}/*1100 50*/
    
   

题意：选两个数，一个减 1，一个加 1，最多操作 k 次。让操作后的序列满足尽量小，但是必须保持非负。 贪心就完事了

#include
   
    using namespace std;const int N = 1e3 + 9;int n, k;int a[N];int main(){   	int t;	cin >> t;	while(t--)	{   		cin >> n >> k;		for(int i = 1; i <= n; ++i)	cin >> a[i];		int j = 1;		while(a[j] < k && j < n) k -= a[j], a[n] += a[j], a[j] = 0, ++j;		//cout << j << endl;		if(a[j] >= k) a[j] -= k, a[n] += k;		for(int i = 1; i <= n; ++i)		{   			if(i > 1) cout << " ";			cout << a[i];		}		cout << endl;	}	return 0;} /*15 71 2 3 4 5*/
   

位运算

找规律，首先发现 当 n 等于 2 的时候，输出 2 的 k 次方即可

第二个规则是说满足所有数的 & 是 0，不是任意两个（一开始理解错了）。

题意：构造一个含 n 个 k 位二进制数的序列，使得序列中所有数按位与的结果为 0 ，且序列和最大，求构造方案数。

思路：对于 n 个数的每一个位，显然都需要至少有一个为 0 ，这样才能保证最后按位与结果为 0 ；由于要求序列和最大，故每一位上应恰好只有一个 0 ，这样对于 k 个位，每个位上的 0 都有 n 种选择，答案为 n 的 k 次方 这个图片好理解，每一列的 0 可以放在任意一行。

假设 k = 3， 那么数据范围是从 0 0 0 -----> 1 1 1 ，包含了所有的排列，又因为数是可以重复的，所以一定有解。

#include
   
    using namespace std;const int mod = 1e9 + 7;int n, k, t;void work(){   	cin >> n >> k;	int N = 1<
    
     > t;	while(t--)		work();	return 0;}
    
   

思维 + 构造 题意就是重新排列每一行，使得让每一列的最小值加和最小

#include
   
    using namespace std;typedef long long LL;const int N = 111;const int inf = 1e9;int n,m,a[N][N],b[N][N];int main(){   	int T,i,j,k,x;	cin>>T;	while(T--){   		cin>>n>>m;		for(i=1;i<=n;i++)			for(j=1;j<=m;j++)				cin>>a[i][j];		for(k = m; k >= 1; k--) 		{   // 从最后一列开始处理，除了最小数所在行，其他行当前位置都是最大数			for(i = 1;i <= n; i++)				sort(a[i] + 1, a[i] + m + 1);			// 每次sort一遍所有行， 让当前行的最小数排在最前			// 最大数排在后边 			x = 1;			for(i = 1; i <= n; i++)				if(a[i][1] < a[x][1])					x = i;			// 寻找矩阵中最小的数所在行 x 			b[x][k] = a[x][1];			a[x][1] = inf;// 把个最小数删去			// 注意，我们现在只处理第 k 列			for(i = 1; i <= n; i++)// 把第k列（除了第x行）每行都放此行还没放的最大数				if(i != x)				{   					b[i][k] = a[i][k], a[i][k] = inf;				}		}		for(i = 1;i <= n; i++)		{   			for(j = 1;j <= m; j++)				cout << b[i][j] << ' ';			cout << endl;		}	}	return 0;}/*13 310 3 28 7 55 1 6*/
   

思维 + 构造 题意：数组 a 大小为 n， 给定一个长度为 n + 2 的数组 b，抛开一个元素 b[i]（不用管了），在另外 n + 1 个数中， 其中任意 n 个数的和是否为另一个数。

#include
   
    using namespace std;int n, t;const int N = 2e5 + 9;int a[N], b[N];int main(){   	cin >> t;	while(t--)	{   		cin >> n;		for(int i = 1; i <= n+2; ++i) scanf("%d", &b[i]);		sort(b+1,b+1+n+2);		long long sum = 0;		for(int i = 1; i <= n + 1; ++i) sum += b[i];		/*for(int i = 1; i <= n + 2; ++i)		{			cout << b[i] << " ";		}cout << endl << sum << endl;*/		int pos = -1;		for(int i = 1; i <= n + 1; ++i)// 先看 b[n+2] 是不是可能为和 		{   			if(sum - b[i] == b[n+2]){   				pos = i;break;			}		}		if(pos != -1)// 扔掉下标为pos元素，b[n+2] 是和		{   			int t = 0;			for(int i = 1; i <= n + 1; ++i)			{   				if(i != pos)				{   					if(t > 0) cout << " ";					++t;					cout << b[i];				}			}			cout << endl;		}		else 		{   			// 再看 b[n+1] 能否为 前 n 项的和			if(sum-b[n+1] == b[n+1])			{   				for(int i = 1; i <= n; ++i)				{   					if(i > 1) cout << " ";cout << b[i];				}				cout << endl;			}			else cout << -1 << endl;		}	}	return 0;}/*1518 2 2 3 2 9 2*/
   

思维 + 构造 题意就是 给你 a 个 0 和 b 个 1，能否把所给的序列变成回文序列。 考虑一些特殊的例子

1. 给定的序列是确定的，但不是回文的
2. 给定的 a 或 b 是小于所给序列中的 0 或 1的
3. 都为奇数肯定不能构造出回文
4. 构造完所有的以后，序列剩余一个 1 和一个 0
   这些例子都需要输出 -1

#include
   
    using namespace std;int a;// 0int b;// 1string s;bool check(){   	int n = s.length();	if(n == 1) return true;	for(int i = 0; i < n / 2; ++i)	{   		if(s[i] != s[n-i-1]) return false;	}	return true;}int main(){   	int t;	cin >> t;	while(t--)	{   		cin >> a >> b;		cin >> s;		if(a&1 && b&1){    // 两个都是奇数肯定不能对称			cout << -1 <
    
     = 2) s[i] = s[n-i-1] = '0', x -= 2;					else if(y >= 2) s[i] = s[n-i-1] = '1', y -= 2;				}			}		if(x & y) {   		/* 构造完剩下一个 0 一个 1		5 2		???1???   ---->   00?1?00   肯定不行了		*/			cout << -1 << endl;continue;		}		else if(x) s[n/2] = '0';// 放中间的		else if(y) s[n/2] = '1';		if(check()) cout << s << endl;		// 最后check一下，因为可能给出一个确定的序列但不是回文		else cout << -1 << endl;	}	return 0;} /*15 2???1???*/
    
   

根据题意模拟就行。

#include
   
    using namespace std;int t, k, n;string s;int main(){   	cin >> t;	while(t--)	{   		cin >> n >> k;		cin >> s;		int l = s.length();		long long sum = 0;		for(int i = 0; i < l; ++i)	if(s[i] == '*'){   			s[i] = 'x'; ++sum;break;			}		for(--l; l >= 0; --l)	if(s[l] == '*'){   			s[l] = 'x'; ++sum;break;			}		//cout << l << endl;		for(int i = 0 ; i < l; ++i)		{   			if(s[i] == 'x')			{   				bool f = 0;				for(int j = i+1; j <= i + k; ++j)					if(s[j] == 'x'){   						f=1;break;					}				if(!f)				{   					int j = i + k;					while(s[j] != '*' && j >= i) --j;					if(s[j] == '*'){   						//cout << j << endl;						++sum;s[j] = 'x';					}				}							}		}		cout << sum << endl;	}	return 0;}
   

思维 + 贪心 题意：任意两个不同的数可以消除，求最后最少剩多少 关于 Max * 2 <= n 的时候答案应该为多少。 当Max * 2 <= n 这种情况下，我们假设为 n 为 5， s1,s2,s3,s4,s5 s4 - s5 —> s4 = s4 - s5, s5 = 0; s3 - s4 —> s3 = s3 - s4, s4 = 0; 仅剩 s1 ,s2, s3

#include
   
    using namespace std;const int N = 2e5 + 9;int t, n;int a[N];int main(){   	cin >> t;	while(t--)	{   		memset(a,0,sizeof(a));		//一定要清空，不然又会出现 上一次没用完的放到下一次了 		cin >> n;		for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);		sort(a,a+1+n);		int Max = 0;		for(int i = 1; i <= n; ++i)		{   			int j = i + 1;			while(a[j] == a[i]) ++j;			Max = max(Max,j-i);			i = j - 1;		}		if(Max * 2 < n) cout << n % 2 << endl;		// 比较难理解 		else cout << 2 * Max - n << endl;		//     n - 2 * (n - Max)	}	return 0;}