T1：区块链
赛场上还以为很难，直接打表，80pts。本来以为还不错，结果一堆人AC，吐血！
算了，还是来说说正解吧，说多了都是血和泪啊啊啊！
先对开头的公式进行变形，得到：
nb/(b-n) xor b =a
通过大量的样例我们可以发现，当b=n+1时，nb/(b-n)取到最大值
这是为什么呢？我们可以来证明一下：
∵ nb/(b-n)是正整数，
∴ (b-n)是nb的因数
∴ b≥n+1
∵ 当b=n+1时，nb取到最大值，而b-n取到最小值
∴ 此时分式nb/(b-n)取到最大值
∴此时nb/(b-n)=n(n+1)=n2 +n
∴ 0＜nb/(b-n)≤n2 +n, b≥n+1
于是现在我们就有做法了：
1.用O(n)的复杂度枚举所有n2的因数
2.再用O(n)枚举所有的因数即可（此处为重点，详见代码）
总复杂度：O(2n)
不多说了，上代码吧
AC CODE
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 ll a,b,c;
5 inline ll G(ll d,ll n){
6 c=n+d,b=n*n/d+n,a=c^b;
7 return a;
8 }
9 void solve(){
10 int n;
11 long long ans=0;
12 scanf("%d",&n);
13 long long tn=1ll*n*n;
14 for(int i=1;i<=n;i++)
15 if(!(tn%i)){ans=max(ans,G(i,n));ans=max(ans,G(tn/i,n));}
16 printf("%lld\n",ans);
17 }
18 int main(){
19 freopen("A.in","r",stdin);
20 freopen("A.out","w",stdout);
21 int T;scanf("%d",&T);
22 while(T){T--;solve();}
23 return 0;
24 }
T2：菜肴
通过分析题意，可以发先所有菜肴的依赖关系形成一个有向图。
又注意到n非常小，因此考虑使用状压DP
设置状态：设f(i,j)表示制作第i种菜肴需要的第j种原料的数量
状态转移：朴素转移f(i,j)即可
注意：设置INF，若f(i,j)超过INF就不往上加了，不然会爆的（才80pts/(ㄒoㄒ)/~~）！
原因：由于是朴素转移f(i,j)，所以这类似于一个二维的斐波那契数列，更准确一点，我们可以称这是一个“斐波那契二维数组”（滑稽）
AC CODE
1 #include<bits/stdc++.h>
2 const int N=1e6+10;
3 using namespace std;
4 long long f[12][N],a[12],b[12],c[50];
5 const long long inf=2e8;
6 int star[N],nex[N],to[N],num;
7 inline void add(int x,int y){
8 nex[++num]=star[x];
9 star[x]=num,to[num]=y;
10 }
11 inline int read(){
12 int x=0;char ch=getchar();
13 while(ch<'0'||ch>'9') ch=getchar();
14 while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
15 return x;
16 }
17 int main(){
18 freopen("B.in","r",stdin);
19 freopen("B.out","w",stdout);
20 int n=read(),m=read(),cnt=0;
21 for(int i=1;i<=n;i++) c[i]=read();
22 for(int i=1;i<=m;i++){
23 int x=read();
24 if(!x) cnt++,a[cnt]=read(),f[cnt][i]=1;
25 else for(int j=1;j<=x;j++) add(i,read());
26 }
27 assert(cnt<=10);
28 for(int x=m;x;x--)
29 for(int i=star[x];i;i=nex[i]){
30 int y=to[i];
31 for(int j=1;j<=cnt;j++)
32 f[j][x]+=f[j][y],f[j][x]=min(f[j][x],inf);
33 }
34 int bas=(1<<n)-1,ans=0;
35 for(int i=1;i<=bas;i++){
36 int an=__builtin_popcount(i),fl=1;
37 if(an<=ans) continue ;
38 for(int k=1;k<=cnt;k++) b[k]=0;
39 for(int j=1;j<=n&&fl;j++)
40 if((i>>(j-1))&1)
41 for(int k=1;k<=cnt;k++){
42 b[k]+=f[k][c[j]];
43 if(b[k]>a[k]) {fl=0;break;}
44 }
45 if(fl) ans=an;
46 }
47 printf("%d",ans);
48 }
注意到第36行的__builtin_popcount()函数了吗？这个函数很神奇，可以在O(1)内求解一个数在二进制下的的1的个数。顺带一提，__builtin_popcountll()是它的long long版本哦~
T3：再买一件
为数不多地A了一道题
赛场上，一开始我觉得这是像一个背包问题，于是使用动态规划，但很快就发现似乎不完全正确：
题目中说，要优先满足最大化购买球衣的数量的条件，然后在此基础上，再尽可能多买签名球衣
因此动态规划的时间复杂度会很高，再加上n也特别大，所以这样只能拿部分分
那么，有没有一种算法，可以用较低的复杂度实现这样呈现出优先级的决策呢？
有的！——反悔贪心
众所周知，贪心算法只能求解局部最优解，因此它本身不具有反悔操作
那么怎么才能实现反悔操作呢？
很简单，可以用一个删除堆（或者用set）来存储反悔操作。如果发现当前不是最优解，那么就使用反悔操作，返回上一步，继续求解。
现在我们可以来思考这道题的解法了：
首先要先满足优先级更高的限制条件：最大化购买球衣的数量。
这很容易实现：直接贪心，将ai从小到大排序，算出最多购买多少球衣，购买这些普通版球衣。
那下一个限制条件怎么满足呢？
这时候就要使用反悔操作了，主要有以下几种操作：
1. 将普通球衣升级为签名版球衣；
2. 购买一个没购买的成员的签名版球衣，替换已购买的一个普通版球衣。
同时为了快速判断当前是否是最优解，需要用可删除堆维护：
1. 已购普通版的最高价格。
2.将已选普通版球衣升级为签名版的最小价格差。
3.没购买的成员的签名球衣的最低价格。
好了，现在就双手奉上大家喜闻乐见的代码吧！
AC CODE
1 #include <bits/stdc++.h>
2 using namespace std;
3 inline long long read(){//忘记写long long了，60pts，祭了/(ㄒoㄒ)/~~
4 long long s=0,w=1;
5 char ch=getchar();
6 while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
7 while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
8 return s*w;
9 }
10 typedef long long LL;
11 typedef pair<int, int> pii;
12 const int Maxn = 400500;
13 const int inf = 2e9;
14 struct node{
15 int a, b, id;
16 } a[Maxn];
17 priority_queue <pii, vector<pii>, greater<pii> > mindel, minb;
18 priority_queue <pii, vector<pii>, less<pii> > maxa;
19 int ans[Maxn], aval[Maxn], bval[Maxn];
20 int T, typ, n, K;
21 LL W;
22 pii get_minb(){
23 while (minb.size()){
24 int id = minb.top().second;
25 if (ans[id] != 0)
26 minb.pop();
27 else break;
28 }
29 if (minb.size() == 0)
30 return make_pair(inf, -1);
31 return minb.top();
32 }
33 pii get_mindel(){
34 while (mindel.size()){
35 int id = mindel.top().second;
36 if (ans[id] != 1)
37 mindel.pop();
38 else break;
39 }
40 return mindel.top();
41 }
42 pii get_maxa(){
43 while (maxa.size()){
44 int id = maxa.top().second;
45 if (ans[id] != 1)
46 maxa.pop();
47 else break;
48 }
49 return maxa.top();
50 }
51 void chosea(int id){
52 ans[id] = 1;
53 maxa.push(make_pair(aval[id], id));
54 mindel.push(make_pair(bval[id] - aval[id], id));
55 }
56 void init(){
57 K = 0;
58 while (maxa.size()) maxa.pop();
59 while (minb.size()) minb.pop();
60 while (mindel.size()) mindel.pop();
61 memset(ans, 0, sizeof ans);
62 }
63 void input(){
64 n=read(), W=read();
65 assert(1 <= n && n <= 200000);
66 assert(1 <= W && W <= (long long) 1e15);
67 for (int i = 1; i <= n; i++){
68 a[i].a=read(), a[i].b=read();
69 assert(0 <= a[i].a && a[i].a <= a[i].b);
70 assert(a[i].b <= min(W, (long long) 1e9));
71 a[i].id = i;
72 aval[i] = a[i].a;
73 bval[i] = a[i].b;
74 }
75 }
76 void output(int op){
77 cout << K << endl;
78 if (typ == 2){
79 int cnt = 0;
80 for (int i = 1; i <= n; i++)
81 cnt += (ans[i] == 2);
82 cout << cnt << endl;
83 } else if (typ == 3){
84 for (int i = 1; i <= n; i++)
85 cout << ans[i] << (i == n ? '\n' : ' ');
86 }
87 }
88 bool cmp(node p,node q){return p.a<q.a;}
89 void solve(){
90 input();
91 init();
92 sort(a + 1, a + n + 1, cmp);
93 for (int i = 1; i <= n; i++)
94 if (W >= a[i].a){
95 W -= a[i].a, K++;
96 chosea(a[i].id);
97 } else break;
98 for (int i = K + 1; i <= n; i++)
99 minb.push(make_pair(a[i].b, a[i].id));
100 for (int i = 1; i <= K; i++){
101 int part1 = get_mindel().first, part2 = inf;
102 if (get_minb().first != inf)
103 part2 = get_minb().first - get_maxa().first;
104 if (part1 < part2){
105 if (W < part1) break;
106 W -= part1;
107 int id = get_mindel().second;
108 ans[id] = 2;
109 } else {
110 if (W < part2) break;
111 W -= part2;
112 int id1 = get_minb().second;
113 int id2 = get_maxa().second;
114 ans[id1] = 2, ans[id2] = 0;
115 minb.push(make_pair(bval[id2], id2));
116 }
117 }
118 output(typ);
119 }
120 int main(){
121 freopen("C.in","r",stdin);
122 freopen("C.out","w",stdout);
123 typ=read(), T=read();
124 assert(typ == 1 || typ == 2 || typ == 3);
125 assert(1 <= T && T <= 20);
126 for (; T--; solve());
127 return 0;
128 }
T4：基因优化
比赛时间不够，直接放弃，去做前面的题目去了
简要题意
一个数列，有一些前缀可以翻转，按顺序翻转一些前缀使字典序最小；N≤300000
按照部分分的分布，步步为营，一步步优化解法
SOLUTION1
暴力枚举每个位置翻或不翻；
时间复杂度O(2N)
SOLUTION2
我们现在想求出，对于前i个数，所能产生的最小的字典序是多少；
我们发现，无论后面的怎么翻，之前的一定是越小越好；
对于相邻两个能翻的位置i,j,(i<j).
前j个的最小值要么是前i个的最小值接上i到j这一段；
要么是i到j的翻转接上前i个的最小值(同时在i和j翻转)。
每次翻转前判断哪种方式更优，O(N)暴力比较。
SOLUTION3
考虑用哈希+二分的方式判断优劣程度。
我们现在要维护这些操作：
尾部插入，头部插入，维护一段的哈希值。
一个朴素的实现就是线段树。
O(N log2 N)
SOLUTION4
其实根本不需要用数据结构维护。
直接用两个队列，记录头插入和尾插入的数。
维护队列的前缀哈希值和后缀哈希值。
用这些一定可以拼出一段的哈希值。
O(N log N)
写得快崩溃了，上代码
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int MAXN = 3e5 + 5;
4 const int MAXM = 6e5 + 9;
5 const int Mod = 998244353;
6 const int P = 1e9 + 7;
7 const int Q = 1e9 + 9;
8 const int GP = 10001;
9 const int GQ = 10005;
10 typedef long long ll;
11 typedef long double ld;
12 typedef unsigned long long ull;
13 template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
14 template <typename T> void chkmin(T &x, T y) {x = min(x, y); }
15 template <typename T> void read(T &x) {
16 x = 0; int f = 1; char c = getchar();
17 for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
18 x *= f;
19 }
20 template <typename T> void write(T x) {
21 if (x < 0) x = -x, putchar('-');
22 if (x > 9) write(x / 10);
23 putchar(x % 10 + '0');
24 }
25 template <typename T> void writeln(T x) {
26 write(x);
27 puts("");
28 }
29 struct info {int x, y; };
30 int power(int x, int y, int P) {
31 if (y == 0) return 1;
32 int tmp = power(x, y / 2, P);
33 if (y % 2 == 0) return 1ll * tmp * tmp % P;
34 else return 1ll * tmp * tmp % P * x % P;
35 }
36 info operator + (info a, info b) {
37 info ans;
38 ans.x = (a.x + b.x >= P) ? (a.x + b.x - P) : (a.x + b.x); ans.y = (a.y + b.y >= Q) ? (a.y + b.y - Q) : (a.y + b.y); return ans;
39 }
40 info operator - (info a, info b) {
41 info ans;
42 ans.x = (a.x - b.x >= 0) ? (a.x - b.x) : (a.x - b.x + P); ans.y = (a.y - b.y >= 0) ? (a.y - b.y) : (a.y - b.y + Q); return ans;
43 }
44 info operator * (info a, int b) {
45 info ans;
46 ans.x = 1ll * a.x * b % P;
47 ans.y = 1ll * a.y * b % Q;
48 return ans;
49 }
50 info operator * (info a, info b) {
51 info ans;
52 ans.x = 1ll * a.x * b.x % P;
53 ans.y = 1ll * a.y * b.y % Q;
54 return ans;
55 }
56 bool operator == (info a, info b) {
57 return a.x == b.x && a.y == b.y;
58 }
59 info base, powb[MAXM];
60 info invb, powi[MAXM], sum[MAXM];
61 void update(int &x, int y) {
62 x += y;
63 if (x >= Mod) x -= Mod;
64 }
65 bool mark[MAXN];
66 int n, m, l, r, ans[MAXM];
67 int a[MAXN], powk[MAXN];
68 void popback() {
69 r--;
70 }
71 void popfront() {
72 l++;
73 }
74 void pushback(int x) {
75 ans[++r] = x;
76 sum[r] = sum[r - 1] + powb[r] * x;
77 }
78 void pushfront(int x) {
79 ans[--l] = x;
80 sum[l - 1] = sum[l] - powb[l] * x;
81 }
82 bool cmp(int s, int t, int len) {
83 int l = 0, r = len;// cerr << len << endl;
84 while (l < r) {
85 int mid = (l + r + 1) / 2;
86 if ((sum[s + mid - 1] - sum[s - 1]) == (sum[t + mid - 1] - sum[t - 1]) * powb[s - t]) l = mid;
87 else r = mid - 1;
88 }
89 if (l == len || ans[s + l] < ans[t + l]) return true; else return false;
90 }
91 int main() {
92 freopen("D.in", "r", stdin);
93 freopen("D.out", "w", stdout);
94 powb[0] = powi[0] = (info) {1, 1};
95 base = (info) {GP, GQ};
96 invb = (info) {power(GP, P - 2, P), power(GQ, Q - 2, Q)}; for (int i = 1; i < MAXM; i++) {
97 powb[i] = powb[i - 1] * base;
98 powi[i] = powi[i - 1] * invb;
99 }
100 powk[0] = 1;
101 for (int i = 1; i < MAXN; i++)
102 powk[i] = 37ll * powk[i - 1] % Mod;
103 int T; read(T);
104 for (int t = 1; t <= T; t++) {
105 // printf("Case %d: ", t);
106 read(n), read(m);
107 for (int i = 1; i <= n; i++)
108 read(a[i]), mark[i] = false;
109 for (int i = 1; i <= m; i++) {
110 int x; read(x);
111 mark[x] = true;
112 }
113 ans[l = r = MAXN] = a[1];
114 sum[l - 1] = (info) {0, 0};
115 sum[l] = powb[l] * a[1];
116 int last = 1;
117 for (int i = 2; i <= n; i++)
118 if (!mark[i]) {
119 int len = i - last;
120 int x = l, length = r - l + 1;
121 for (int j = last + 1; j <= i; j++) {
122 pushback(a[j]);
123 pushfront(a[j]);
124 }
125 int y = l;
126 // cerr << length << endl;
127 if (cmp(x, y, length + len)) {
128 while (len--) popfront();
129 } else {
130 while (len--) popback();
131 }
132 last = i;
133 }
134 while (last != n)
135 pushback(a[++last]);
136 int final = 0;
137 for (int i = l; i <= r; i++)
138 update(final, 1ll * powk[i - l] * ans[i] % Mod);
139 writeln(final);
140 }
141 return 0;
142 }
总结与归纳
本次模拟赛，3.5h，总分400pts，得分260pts 。
T1主要考察基本数论。这道题没有把分拿足，被别人来开差距，实属可惜
T2主要考察状压DP。由于状态可能存在爆long long 的情况，因此需要设置一个上限INF，避免出现RE
T3主要考察对贪心算法的应用以及利用堆维护数据
T4主要考察哈希的综合应用，难度较大！
此之谓：“不开long long见祖宗”乎！
划水任务完成喽，溜了溜了ε=ε=ε=(~￣▽￣)~
标签：info,10.2,int,冲刺班,2023,long,id,ans,void From： https://www.cnblogs.com/zhipuqingnian/p/17740357.html