题目给出 t 组数据，对于每组数组给出一个n（n为偶数），将21 22 ........ 2n n 个数分成等份的两部分，求这两部分差的绝对值最小是多少。
将 2n 和（n/2）个较小的分在一起，剩下的分在一起，便可保证结果最小，然后通过列举几个情况，便可推出规律。
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> using namespace std; const long long N = 1e10 + 7; const int maxn = 2e5 + 5; const long long INF = 8e18; typedef long long ll; #define for0(i,n) for(int i = 0;i < n;i++) #define for1(i,n) for(int i = 1;i <= n;i++) int main() { int t; cin >> t; while(t--){ ll num = 0; int n; cin >> n; for(int i = 0;i < n;i += 2){ num = 2*num+2; } cout << num << endl; } return 0; }
题目给出 t 组数据，对于每组数组给出 n , m，然后再给出 n 个数的数列。让你通过在数列中插入若干数，使得数列每m个连续数的和都相等，若不能构造则输出-1。
首先想到将n个数对应每个位置变成一个含数列中所有数的一个数列，这样便可符合题目条件。所有当给出的数列中不相等的数目大于m时，遍不可构造，另外情况下可构造。首先遍历数列统计出不相同的数的个数并存入另外的数组总，然后根据与m的个数控制输出形式，如果不相同的数的个数小于m再找一个数组外的数凑出。
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> using namespace std; const long long N = 1e10 + 7; const int maxn = 2e5 + 5; const long long INF = 8e18; typedef long long ll; #define for0(i,n) for(int i = 0;i < n;i++) #define for1(i,n) for(int i = 1;i <= n;i++) int a[110],sign[110]; int main() { int t; cin >> t; while(t--){ int n,m,num,j = 0,temp; cin >> n >> m; for0(i,n){ cin >> num; if(!sign[num]){ sign[num]++; a[j++] = num; } } for1(i,100){ if(!sign[i]){ temp = i; //寻找一个没有出现的数，用于后面可能的填充。 break; } } if(j > m) cout << -1 << endl; else{ cout << n*m << endl; for(int y = 0;y < n;y++){ for0(i,j){ cout << a[i] << " "; } for0(i,m-j){ cout << temp << " "; } } cout << endl; } memset(a, 0, sizeof(a)); memset(sign, 0, sizeof(sign)); } }
每组数据给出的 x , y（假设x>y）,则比较 x~y用操作1，然后用操作2，和 只用操作1的费用就可。
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> using namespace std; const long long N = 1e10 + 7; const int maxn = 2e5 + 5; const long long INF = 8e18; typedef long long ll; #define for0(i,n) for(int i = 0;i < n;i++) #define for1(i,n) for(int i = 1;i <= n;i++) int main() { int t; cin >> t; while(t--) { ll a,b,x,y; cin >> x >> y >> a >> b; if(x < y) swap(x,y); ll num1 = a * (x+y); ll num2 = a * (x-y) + b * y; cout << min(num1,num2) << endl; } return 0; }
题目给出 t 组数据，对于每组数组给出一个01串，让你找出一个新串长度小于大于之前串的二倍，并且给出的串是新串的子串，还要使新串的循环节最少。
由此可以想到，当给出的串是全1串或全0串时，直接输出原串便可，反之，则以 “10”或“01”作为循环，输出 l 遍（原串长度为 l )。
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> using namespace std; const long long N = 1e10 + 7; const int maxn = 2e5 + 5; const long long INF = 8e18; typedef long long ll; #define for0(i,n) for(int i = 0;i < n;i++) #define for1(i,n) for(int i = 1;i <= n;i++) int main() { int t; cin >> t; while(t--) { string s; int num1 = 0,num2 = 0; cin >> s; for0(i,s.size()){ if(s[i] == ‘0‘) num1 = 1; if(s[i] == ‘1‘) num2 = 1; if(num1&&num2) break; } if(num1&&num2){ for0(i,s.size()) cout << "10"; cout << endl; } else{ cout << s << endl; } } return 0; }
对于每组数据给出n，a，b，c，d，本题假设判断 [ n*(a-b) , n*(a+b) ] 与 [ c-d , c+d ] 是否有交集。
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> using namespace std; const long long N = 1e10 + 7; const int maxn = 2e5 + 5; const long long INF = 8e18; typedef long long ll; #define for0(i,n) for(int i = 0;i < n;i++) #define for1(i,n) for(int i = 1;i <= n;i++) int main() { int t; cin >> t; while(t--){ int a,b,c,d,n; cin >> n >> a >> b >> c >> d; if( n*(a-b) <= (c+d) && n*(a+b) >= (c-d) ) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
题目给出 t 组数据，对于每组数组给出 n,k 接下来给出 n个数代表山的高度。需要寻找 连续的 k座山中存在最多的顶峰区间（顶峰:ai > ai+1 且ai > ai-1），要求输出将该区间单独分割需要多少个门，以及该区间的左位置（若有多个答案，输出最小的那个）。
先对每一个山峰遍历，标记一下它是不是顶峰，然后求一下前缀和得到区间顶峰数（然而划定区间内不一定都是顶峰，需要再判断一下边界，也可收缩一下区间）（详情看代码注释）。
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> using namespace std; const long long N = 1e10 + 7; const int maxn = 2e5 + 5; const long long INF = 8e18; typedef long long ll; #define for0(i,n) for(int i = 0;i < n;i++) #define for1(i,n) for(int i = 1;i <= n;i++) int sign[maxn],a[maxn]; int main() { int t; cin >> t; while(t--){ int n,k; int point = 1,maxnum = 0; cin >> n >> k; for1(i,n) cin >> a[i]; for(int i = 2;i < n;i++){ if(a[i] > a[i-1] && a[i] > a[i+1]) sign[i]++; } for1(i,n) sign[i] += sign[i-1]; for(int i = 1;i <= n-k+1;i++){ int temp = sign[i+k-2] - sign[i];
//此处其实求解是 [i , i+k-1]区间的顶峰数，然而这样求解可能会将边界的两个山峰错认为是顶峰，所以这里[i+1 , i+k-2]区间的峰数才是正确答案 if(temp > maxnum){ maxnum = temp; point = i; } } cout << maxnum+1 << " " << point << endl; memset(sign,0,sizeof(sign)); } return 0; }
原文：https://www.cnblogs.com/emhhbw/p/12918994.html