2021 icpc南京（A,M,C,H,J,D）

题意：
n * m的矩阵，每个格子上都有一只袋鼠，要求通过U,D,L,R，使得所有袋鼠到达(a,b)，要求最多进行3 * (n-1)次操作，一定有解

首先,要使得所有袋鼠都到达同一个点,首先必须让所有袋鼠到一个角落
题目说一定有解,那就四个角落分别试一遍,哪种情况操作数小于等于3*(n-1),直接输出操作序列

做这题的时候脑子抽了，n-a一直想成是n-a+1，n-b想成是n-b+1，属于是数数不会数了，然后还觉得肯定没问题，一直交，一直wa

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,a,b;
void solve() {cin>>n>>a>>b;//左上角if(n-1+n-1+a-1+b-1<=3*(n-1)){for(int i=0;i<n-1;i++) cout<<'L';for(int i=0;i<n-1;i++) cout<<'U';for(int i=0;i<a-1;i++) cout<<'D';for(int i=0;i<b-1;i++) cout<<'R';return;}//右上角if(n-1+n-1+a-1+n-b<=3*(n-1)){for(int i=0;i<n-1;i++) cout<<'R';for(int i=0;i<n-1;i++) cout<<'U';for(int i=0;i<a-1;i++) cout<<'D';for(int i=0;i<n-b;i++) cout<<'L';return;}//左下角if(n-1+n-1+n-a+b-1<=3*(n-1)){for(int i=0;i<n-1;i++) cout<<'L';for(int i=0;i<n-1;i++) cout<<'D';for(int i=0;i<n-a;i++) cout<<'U';for(int i=0;i<b-1;i++) cout<<'R';return;}//右下角for(int i=0;i<n-1;i++) cout<<'R';for(int i=0;i<n-1;i++) cout<<'D';for(int i=0;i<n-a;i++) cout<<'U';for(int i=0;i<n-b;i++) cout<<'L';
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

题意：

n个数围成一个圆，操作是选择相邻的两个数，用前一个数减后一个数的值替换掉前一个数，删去后一个数，直到最后只剩一个数，问最后一个数最大是多少

举个例子
1 -3 2
假设最后留下-3
那么我们可以对-3,2操作,变为1 -5,再对-5,1操作,变为-6,实际上过程是-3减去2,减去1
我们也可以先对2,1操作,变为-3 1,再对-3,1操作,变为-4,实际上过程是-3减去2,加上1
综上,可以发现,假设我们留下的是x,那么它肯定是原值,然后减去它的后一个数的原值,其它我们都可以控制,想加就加,想减就减,要使得结果最大,加上其它数的绝对值

不要忘了特判n为1的情况

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e6+10;
int a[N];
int n;
void solve() {cin>>n;for(int i=0;i<n;i++) cin>>a[i];if(n==1){cout<<a[0]<<endl;return;}int sum=0;for(int i=0;i<n;i++) sum+=abs(a[i]);int ans=-1e18;for(int i=0;i<n;i++){//枚举最后留下的是a[i]int last=(i+1)%n;int result=sum-abs(a[i])-abs(a[last])+a[i]-a[last];ans=max(ans,result);}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

题意：

给定一个长度为 nn 的整数序列 a1,a2,⋯,an和一个整数 k ，最多可以进行一次下面的运算：选择长度为 1≤l≤r≤n 的两个整数 l和 r 并将 k 加到 ai 中的每一个 l≤i≤r 中。注意，不执行此操作也是可以的。如果您选择执行(或不执行)最佳操作，请计算整个序列中众数的次数最大是多少

map 的查找和插入操作虽然在平均情况下是 O(log⁡n)，但在实际运行中可能会有较大的常数因子，尤其是在哈希冲突较多的情况下

unordered_map 在最坏情况下（哈希冲突较多时）的时间复杂度可能退化为 O(n)，而不是平均情况下的 O(1)。如果输入数据导致大量哈希冲突，性能会显著下降

该题用map和unordered_map均会超时，如果可以用数组进行桶计数，尽量用数组，如果有统计负数个数的情况，可以加一个偏移量

首先,问最大,肯定先想到二分,然后发现不怎么能写,此时我们在纸上写一个1.二分,然后我们先略过,想别的方法,因为不能完全排除某种方法时,我们需要想其它的方法,为了避免总是绕回到这种方法,所以先记下来,这样就可以安心想另一种方法了,后面尝试了各种方法之后还可以看看之前记录的
我们可以注意到,由于只能加k,然后假设原本为x,那么后面就会变成x+k,所以单独考虑x,x+k
我们考虑x-k最终变成了x,其它都不需要考虑,于是单独把它们按顺序存起来,相对顺序不变就行,思考如果选择区间使得最终x的个数最大,这里用前缀和,挺难想到的,后面总结一下如何想到
sumx_k[i]表示x-k的前缀和个数,sumx[i]表示x的前缀和个数
假设选择区间[l,r],那么最终x的个数即为[l,r]中x-k的个数加上[1,l-1]和[r+1,len]中x的个数,也就是sumx[len]-(sumx[r]-sumx[l-1])+(sumx_k[r]-sumx_k[i-1]),移项得到sumx[len]+sumx_k[r]-sumx[r]+sumx[l-1]-sumx_k[l-1]
其中sumx[len]固定,sumx_k[r]-sumx[r]当r固定时也是固定的,那么只要在r固定的情况下,维护sumx[l-1]-sumx_k[l-1]的最大值即可,扫一遍即可

总结一下trick：

当有两个量时，区间问题，那么用前缀和就会出现sum1[r]-sum1[l-1]和sum2[r]-sum2[l-1]，那么sum1[r]和sum2[r]合在一起，sum1[l-1]和sum1[l-1]合在一起，就会大大简化

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e6+10,M=4e6+10;
int a[N];
int cnt[M];
int sumx_k[M],sumx[M];
int n,k;
vector<int>s[M];
void solve() {cin>>n>>k;int ans=0;for(int i=1;i<=n;i++) {cin>>a[i];a[i]+=2e6;cnt[a[i]]++;ans=max(ans,cnt[a[i]]);}if(k==0){cout<<ans<<endl;return;}for(int i=1;i<=n;i++) {s[a[i]].push_back(a[i]);s[a[i]+k].push_back(a[i]);}for(int i=0;i<=4e6;i++){if(!s[i].size()) continue;int len=s[i].size();for(int j=0;j<len;j++){sumx_k[j+1]=sumx_k[j]+(s[i][j]==i-k);sumx[j+1]=sumx[j]+(s[i][j]==i);}int pre=-2e9;for(int j=1;j<=len;j++){pre=max(pre,sumx[j-1]-sumx_k[j-1]);ans=max(ans,sumx[len]+sumx_k[j]-sumx[j]+pre);}}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

题意：

树，在 i -th顶点上最初有 ai 只水晶蝇。当帕蒙到达一个顶点时，她可以立即捕捉到顶点上剩余的所有水晶蝇。然而，水晶蝇很胆小。当帕蒙到达一个顶点时，相邻顶点上的所有冰蝇都会受到干扰。对于 i-th顶点，如果顶点上的水晶蝶在 t′-th秒开始时第一次受到干扰，那么它们就会在 (t′+ti)-th秒结束时消失。

在 0秒开始时，Paimon到达顶点 1，并在 1秒开始前停留在那里。然后在接下来的每一秒开始时，她可以从两个操作中选择一个：

• 移动到当前顶点的一个相邻顶点，并在下一秒开始前停留在那里(如果目的地的水晶蝇将在该秒结束时消失，她仍然可以捕捉到它们)。
• 在下一秒开始前停留在当前顶点不动。

计算 在 $10^{10^{10^{10^{10}}}}$秒内最多可以捕捉多少只水晶蝇

树形dp
如果t只有1和2的话,那么每次到达一个点x时,惊动了x的子节点,只能捕捉到x的其中一个子节点,所以就是设dp[x]为不算上节点x捕捉的最大数量,那么dp[x]=max(dp[x],sum[x]+maxn),其中sum[x]表示x的子节点的dp和,maxn表示x的子节点的最大水晶蝇数量
但是现在t还有3,其中1和2的话还是只能选一个,当然也可以去选择一个3,然后现在还可以去选择一个3,但是代价是第一次选择的那个点的所有子节点全部不能捕捉,
dp[x]=max(dp[x],sum[x]-dp[y]+sum[y]+a[p]+a[y],其中p为第二次选择的t为3的点
我们需要去枚举第一个点和第二个点的选择,将各个点作为第一个点,如果第一个点是1和2的话,那么第二个的点是t为3且水晶蝇数量最大的那个最优,如果第一个点t为3,但不是水晶蝇数量最大的,那么第二个点也是t为3且水晶蝇数量最大的那个最优,如果第一个点t为3且水晶蝇数量最大,那么第二个点t为3,且水晶蝇数量第二大最优
最终答案是dp[1]+a[1]

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
struct node{int a,t;
}q[N];
bool cmp(int x,int y){return q[x].a>q[y].a;
}
int sum[N];
int n;
vector<vector<int>>e(N);
int dp[N];
int dfs(int u,int fa){sum[u]=0;if(u!=1&&(int)e[u].size()==1){//叶子节点return dp[u]=0;}vector<int>res1,res2;int maxn=0;for(auto v:e[u]){if(v==fa) continue;sum[u]+=dfs(v,u);maxn=max(maxn,q[v].a);if(q[v].t==3) res1.push_back(v);else res2.push_back(v);}dp[u]=sum[u]+maxn;if(res1.size()) sort(res1.begin(),res1.end(),cmp);if(res2.size()) sort(res2.begin(),res2.end(),cmp);if(res1.size()) {for(int i=1;i<(int)res1.size();i++){int y=res1[i];dp[u]=max(dp[u],sum[u]-dp[y]+sum[y]+q[res1[0]].a+q[y].a);}for(int i=0;i<(int)res2.size();i++){int y=res2[i];dp[u]=max(dp[u],sum[u]-dp[y]+sum[y]+q[res1[0]].a+q[y].a);}}if((int)res1.size()>=2){int x=res1[1],y=res1[0];dp[u]=max(dp[u],sum[u]-dp[y]+sum[y]+q[x].a+q[y].a);}return dp[u];
}
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>q[i].a;for(int i=1;i<=n;i++) cin>>q[i].t;for(int i=1;i<=n;i++) e[i].clear(),dp[i]=0;for(int i=0;i<n-1;i++){int u,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs(1,-1);
//	for(int i=1;i<=n;i++) cout<<dp[i]<<' ';
//	cout<<endl;cout<<dp[1]+q[1].a<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

题意：

锁上有两个整数 a 和 b 。重云可以执行以下三种类型的操作任意多次：

• 从 a 和 b 中减去 1 ；
• 将 a 和 b 都加上 1 ；
• 将 a 和 b 除以它们的一个共同质因数(即除以一个质数g ，其中 a 和 b 都能被 g 整除)。

如果 a 或 b 或都变成 1 ，盒子就会被打开。为了帮助崇云尽快取回冰淇淋，请告诉他解锁盒子所需的最少运算次数

trick:
若a%x=0,b%x=0,则(a-b)%x=0,所以找a和b的共同质因数,就是找abs(a-b)的质因数

a和b同时加1或者同时减1,它们的差是不变的,然后同除以g,则它们的差变为abs(a-b)/g

考虑记忆化搜索,dfs(a,c),其中a为两数较小的那一个,c为b-a
然后如果a为1,那么直接返回0,如果c为1,那么a和b互质,只能一直减1,所以返回a-1
对于dfs(a,c),我们在枚举c的质因数d时,我们肯定是想着让a和b先通过加1或者减1来变成d的倍数,这样就可以同除以d了,一定是变成最近的d的倍数,否则肯定是不优的

在搜索的过程中,c会不断除以它的质因数,1e9最多除以30次质因数,因为2的30次就达1e9了,故在搜索的过程中,第二维c最多有30种状态

第一维的数虽然可能随着除以质因子的顺序不同而不同，但是向上向下取整的差别是1，猜测应该不会多太多

虽然我不会分析复杂度，但是可以测试一下

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int>PII;
vector<int>s;
set<PII>q;
void dfs(int a,int c){if(a==1||c==1) return;if(q.count({a,c})) return;q.insert({a,c});for(auto d:s){if(c%d==0){dfs(a/d,c/d);dfs(a/d+1,c/d);}}
}
int a,c;
void solve() {cin>>a>>c;int x=c;for(int i=2;i<=x/i;i++){if(x%i==0){s.push_back(i);while(x%i==0) x/=i;}}dfs(a,c);cout<<q.size()<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

a=1000000000 c=100 q.size()=15
a=1000000000 c=500000000 q.size()=177
所以可以发现,总共的状态数很少很少,时间上完全够

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int>PII;
map<PII,int>mp;
vector<int>s;
int a,b;
int dfs(int a,int c){if(a==1) return 0;if(c==1) return a-1;if(mp.count({a,c})) return mp[{a,c}];int minn=a-1;for(auto d:s){if(c%d==0){int res=a%d;//差多少可以变成d的倍数int tmp1=res+1+dfs(a/d,c/d);int tmp2=d-res+1+dfs(a/d+1,c/d);minn=min(minn,tmp1);minn=min(minn,tmp2);}}return mp[{a,c}]=minn;
}
void solve() {cin>>a>>b;if(a>b) swap(a,b);mp.clear();s.clear();int c=b-a;int x=c;for(int i=2;i<=x/i;i++){if(x%i==0){s.push_back(i);while(x%i==0) x/=i;}}if(x>1) s.push_back(x);cout<<dfs(a,c)<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

题意：

给定这样一个排序方法：

for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i]<a[j]) swap(a[i],a[j]);}
}

按照此种方法排序，问排序前i个数的交换次数是多少，回答i=1~n

很明显,是一个规律题,需要通过找规律发现该题的特殊性质,从而找到突破口
手玩或者打表

6
3 4 5 1 5 2
i=1
4 3 5 1 5 2
5 3 4 1 5 2
i=2
3 5 4 1 5 2
i=3
3 4 5 1 5 2
i=4
1 4 5 3 5 2
1 3 5 4 5 2
1 3 4 5 5 2
i=5
i=6
1 2 4 5 5 3
1 2 3 5 5 4
1 2 3 4 5 5

首先第一次单独考虑，最终是将最大的那个数换到了第一个位置，因为最大的数这一特殊性，后面就有比较明显的规律了

第i次开始前，1_{i-1个数都已经排好序了，并且第i-1个数是整个序列中最大的，交换次数为1}i-1中大于i的种数（用树状数组）

要求排好前i个(i=1~n)的交换次数，如果分别求，必定超时，所以肯定是存在一个递推的关系

设maxn=a[1]~a[i-1]中的最大值

如果a[i]<maxn，那么1_{i-1趟交换次数均一样，第i躺多了的交换次数为1}i-1中大于i的种数

如果a[i]=maxn，那么交换次数一样

如果a[i]<maxn，进行打表：

7
3 4 5 1 5 2 6
i=1
4 3 5 1 5 2 6
5 3 4 1 5 2 6
6 3 4 1 5 2 5
i=2
3 6 4 1 5 2 5
i=3
3 4 6 1 5 2 5
i=4
1 4 6 3 5 2 5
1 3 6 4 5 2 5
1 3 4 6 5 2 5
i=5
1 3 4 5 6 2 5
i=6
1 2 4 5 6 3 5
1 2 3 5 6 4 5
1 2 3 4 6 5 5
1 2 3 4 5 6 5
i=7
1 2 3 4 5 5 6

与上一个例子进行比较，发现第一次排序，相比前者多了一个6交换到第一个位置，5交换到最后的位置，这样第一次排序多了一次交换

然后在第二个5之前，6就相当于上一个例子的5，排序次数一样，当到了第二个5时，发现交换次数每次都比前者多1次，也就是多了第二个5开始到最后的个数再+1

继续验证：

4
3 4 3 4
i=1
4 3 3 4
i=2
3 4 3 4
i=3
3 3 4 4
i=4

5
3 4 3 4 6
i=1
4 3 3 4 6
6 3 3 4 4
i=2
3 6 3 4 4
i=3
3 3 6 4 4
i=4
3 3 4 6 4
i=5
3 3 4 4 6

仍然符合上述规律

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N];
int tr[N];
int ans[N];
bool vis[N];
int n;
int lowbit(int x) {return x & -x;
}
int sum(int x) {int res = 0;while (x) res += tr[x], x -= lowbit(x);return res;
}
void add(int x, int c) {while (x <= n) tr[x] += c, x += lowbit(x);
}
void solve() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i],vis[i]=false,tr[i]=0;int maxn = 0;map<int, int>mp;int pos = -1;add(a[1],1);vis[a[1]]=true;maxn=max(maxn,a[1]);mp[maxn]++;ans[1]=0;for (int i = 2; i <= n; i++) {if (a[i] == maxn) ans[i] = ans[i - 1];else if (a[i] < maxn) ans[i] = ans[i - 1] + sum(n) - sum(a[i]);else {if (pos != -1) ans[i] = ans[i - 1] + i - pos + 2;else ans[i] = ans[i - 1] + 2;}if(a[i]==maxn){mp[maxn]++;if(mp[maxn]==2) pos=i;}else if(a[i]>maxn){maxn=a[i];mp[maxn]++;pos=-1;}if (!vis[a[i]]) {add(a[i], 1);vis[a[i]] = true;}}for (int i = 1; i <= n; i++) {cout << ans[i];if (i != n) cout << ' ';}cout << endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--) {solve();}return 0;
}