2023信友队提高组复赛冲刺班 10.2赛后总结-526互联

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)=n²+n

∴ 0＜nb/(b-n)≤n²+n, b≥n+1

于是现在我们就有做法了：

1.用O(n)的复杂度枚举所有n²的因数

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）来存储反悔操作。如果发现当前不是最优解，那么就使用反悔操作，返回上一步，继续求解。

现在我们可以来思考这道题的解法了：

首先要先满足优先级更高的限制条件：最大化购买球衣的数量。

这很容易实现：直接贪心，将a_i从小到大排序，算出最多购买多少球衣，购买这些普通版球衣。

那下一个限制条件怎么满足呢？

这时候就要使用反悔操作了，主要有以下几种操作：

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

$<strong><span class="math math-inline">按照部分分的分布，步步为营，一步步优化解法$

$<span class="math math-inline">SOLUTION1$

暴力枚举每个位置翻或不翻；
时间复杂度O(2^N)

SOLUTION2

我们现在想求出，对于前i个数，所能产生的最小的字典序是多少；
我们发现，无论后面的怎么翻，之前的一定是越小越好；
对于相邻两个能翻的位置i,j,(i<j).
前j个的最小值要么是前i个的最小值接上i到j这一段；
要么是i到j的翻转接上前i个的最小值(同时在i和j翻转)。
每次翻转前判断哪种方式更优，O(N)暴力比较。

SOLUTION3

考虑用哈希+二分的方式判断优劣程度。
我们现在要维护这些操作：
尾部插入，头部插入，维护一段的哈希值。
一个朴素的实现就是线段树。
O(N log² 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 }