CF
Problem - 466C - Codeforces
前缀和，三等分
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=5e5+10;
LL a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i];a[i] += a[i - 1];}if(n<3||a[n]%3!=0){cout << 0 << endl;return 0;}LL cut = a[n] / 3;LL ans = 0, cnt = 0;for (int i = 1; i <= n;i++){if(i>1&&i<n&&a[i]==cut*2){ans += cnt;}if(i<n-1&&a[i]==cut)cnt++;}cout << ans << endl;
}
Problem - 1038D - Codeforces
观察题目，虽然限制只能吃相邻史莱姆，但是任意两只都是可以相互吃的
比如
a b c d
(a(bc)) 吞 d
所以可以当作任意组合
只要保证一个数负数（被吃），一个数正数（吃）
其他中间的找最大值即可
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=5e5+10;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i];}if(n==1){cout<<a[1]<<endl;return 0;}sort(a + 1, a + 1 + n);LL ans = 0;ans -= a[1];for (int i = 2; i < n;i++){ans += max(a[i], -a[i]);}ans += a[n];cout << ans << endl;
}
Problem - 798C - Codeforces
思维好题
题目简述：每次操作，他可以选择一个下标 \(i(1⩽i<n)\)，删除 \(a_i\) 和 \(a_{i+1}\)，然后把 \(a_i−a_{i+1}\) 和 \(a_i+a_{i+1}\) 放回这两个位置上。
推导：
操作定义为：
\[(a_i, a_{i+1}) \to (x, y) = (a_i - a_{i+1},\, a_i + a_{i+1})
\]
于是：
\[\gcd(x, y) = \gcd(a_i - a_{i+1},\, a_i + a_{i+1})
\]
因为：
\[(a_i + a_{i+1}) - (a_i - a_{i+1}) = 2 a_{i+1}
\]
所以可以得到：
\[\gcd(x, y) = \gcd(a_i - a_{i+1},\, 2 a_{i+1}) \]
利用 [[最大公约数和最小公倍数#^01146a| gcd性质]]：
\[\gcd(a - b, b) = \gcd(a, b)
\]
得到：
\[\gcd(a_i - a_{i+1},\, a_{i+1}) = \gcd(a_i, a_{i+1})
\]
设：
\[d = \gcd(a_i, a_{i+1})
\]
那么 \(d\) 一定能整除 \(a_i - a_{i+1}\) 和 \(a_{i+1}\)。因此：
\[\gcd(a_i - a_{i+1},\, 2 a_{i+1}) = \text{可能是 } d \text{ 或 } 2d
\]
即对于（把 \(a_i−a_{i+1}\) 和 \(a_i+a_{i+1}\) 放回这两个位置上），只有可能把gcd变两倍或不变
也就是说：
\[\text{新 gcd} = \text{原 gcd} \times (\text{可能增加一个因子 } 2)
\]
| 原组合 | 操作后奇偶性 | 需要几次操作变偶偶？ |
|---|---|---|
| 偶 偶 | 偶 偶 | 0 |
| 奇 奇 | 偶 偶 | 1 |
| 奇 偶 | 奇 奇 | 2 |
| 偶 奇 | 奇 奇 | 2 |
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=5e5+10;
int a[N];
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;
}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;int g = 0;for (int i = 1; i <= n;i++){cin >> a[i];g = gcd(g, a[i]);}if(g>1){cout << "YES\n";cout << 0 << endl;return 0;}int i = 1,j = 1;int ans = 0;while(i<=n){while(i<=n&&a[i]%2==0)i++;j = i;while(j<=n&&a[j]%2)j++;int len = j - i;ans += len / 2;if(len%2)ans += 2;i = j;}cout << "YES\n";cout << ans << endl;
}
天梯赛L2
L2-008 最长对称子串 - 团体程序设计天梯赛-练习集
字符串
\(O(n)\)
注意，考虑奇数和偶数对称的不同情况
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
int sol(string s,int l,int r){while(l>=0&&r<s.size()&&s[l]==s[r]){l--, r++;}return r - l - 1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string s;getline(cin, s);int n = s.size();int ans = 0;for (int i = 0; i < n;i++){int len1 = sol(s, i, i);//奇数int len2 = sol(s, i, i + 1);//偶数ans = max(ans, max(len1, len2));}cout << ans << endl;
}
L2-009 抢红包 - 团体程序设计天梯赛-练习集
结构体排序
注意单位，抢到是（分），最后统计要是（元）
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=1e4+10;
struct node{int id;int cnt;LL money;bool operator<(const node &x)const{if(money!=x.money){return money > x.money;}else if(cnt!=x.cnt){return cnt > x.cnt;}else{return id < x.id;}}
} a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){a[i].id = i;int k;cin >> k;for (int j = 1; j <= k;j++){int id, mm;cin >> id >> mm;a[id].money += mm;a[id].cnt++;a[i].money -= mm;}}sort(a + 1, a + 1 + n);for (int i = 1; i <= n;i++){cout << a[i].id << " ";cout <<fixed<<setprecision(2)<< (double)a[i].money / 100.0;cout << endl;}
}
L2-010 排座位 - 团体程序设计天梯赛-练习集
并查集，和洛谷的P1892 [BalticOI 2003] 团伙 - 洛谷 不太一样
洛谷这题是敌人的敌人是朋友，可以看看,比这个L2-010难一点点，要加点思维
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=105;
int fa[N];
bool bad[N][N];
int find(int x){if(x!=fa[x])fa[x] = find(fa[x]);return fa[x];
}
void merge(int a,int b){a = find(a);b = find(b);if(a!=b)fa[a] = b;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m, k;cin >> n >> m >> k;for (int i = 1; i <= n;i++){fa[i] = i;}int a, b, op;for (int i = 1; i <= m;i++){cin >> a >> b >> op;if(op==1){merge(a, b);}else{bad[a][b] = 1;bad[b][a] = 1;}}bool isf, ise;while(k--){cin >> a >> b;isf = (find(a) == find(b));ise = bad[a][b];if(isf&&!ise){cout << "No problem\n";}else if(!isf&&!ise){cout << "OK\n";}else if(isf&&ise){cout << "OK but...\n";}else{cout << "No way\n";}}
}
ABC434
D - Clouds
二维差分
难点在怎么找删除之后为空的点
这时再开一个二维数组，存每个点被覆盖的编号之和，然后只要统计a[i][j]=1只被一朵云覆盖的编号
注意：
b数组要开LL
cnt[]里是编号，大小为2e5
还有注意输入！！！
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2010;
LL a[N][N],b[N][N];//注意！！！
int cnt[200010];//注意！！！int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;int x, y, xx, yy;for (int i = 1; i <= n;i++){cin >> x >> xx >> y >> yy;//注意a[x][y]++;a[x][yy + 1]--;a[xx + 1][y]--;a[xx + 1][yy + 1]++;//算编号和b[x][y] += i;b[x][yy + 1] -= i;b[xx + 1][y] -= i;b[xx + 1][yy + 1] += i;}int c0 = 0;for (int i = 1; i <= 2000;i++){for (int j = 1; j <= 2000;j++){a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];if(!a[i][j])c0++;if(a[i][j]==1)cnt[b[i][j]]++;}}for (int i = 1; i <= n;i++){cout << c0 + cnt[i] << endl;}
}
E - Distribute Bunnies
图论
连通块问题，环
注意：由于范围很大-2e9到2e9，不能用vector
所以用map<int,vector<int>>mp
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
map<int, vector<int>> mp;
map<int, bool> vis;
int cnt, edge;
void dfs(int u){vis[u] = 1;cnt++;for(int v:mp[u]){if(!vis[v]){dfs(v);}edge++;//因为有环的可能，所以统计总边数}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){int x, r;cin >> x >> r;mp[x - r].push_back(x + r);mp[x + r].push_back(x - r);}int ans = 0;for(auto x:mp){auto a = x.first;auto b = x.second;if(!vis[a]){cnt = edge = 0;dfs(a);edge /= 2;//无向边使得每一个边都被统计两次ans += min(cnt, edge);//1.该连通块是树//得到的不同点最大数 = edge（边数）//2.该连通块是环//得到的不同点最大数是 = cnt（点数）}}cout << ans << endl;
}