2021年11月的做题记录
杂题选做
最后一个月的做题记录。从NOIP开始，在NOIP结束。
P1063 [NOIP2006 提高组] 能量项链
#include
#include
using namespace std;
const int N=1005;
int n,l[N],r[N],dp[N][N],ans;
int main() {
ios::sync_with_stdio(false);
cin>>n;
for (int i=1; i<=n; i++) {
cin>>l[i];
l[i+n]=l[i];
r[i-1]=l[i];
r[i-1+n]=r[i-1];
}
r[2*n]=l[1];
for (int len=2; len<=n; len++)
for (int j=1; j+len-1<=2*n; j++) {
int t=j+len-1;
for (int k=j; k<=t-1; k++)
dp[j][t]=max(dp[j][t],dp[j][k]+dp[k+1][t]+l[j]*r[k]*r[t]);
if (len==n)
ans=max(ans,dp[j][t]);
}
cout< P3554 [POI2013]LUK-Triumphal arch
给一颗 n 个节点的树（\(n \le 3 \times 10^5\)），初始时 1 号节点被染黑，其余是白的。两个人轮流操作，一开始 B 在 1 号节点。每一轮，A 选择 k 个点染黑，然后 B 走到一个相邻节点，如果 B 当前处于白点则 B 胜，否则当 A 将所有点染为黑点时 A 胜。求能让 A 获胜的最小的 k 。
考虑二分k，对于每一个k进行树形dp，保存每个结点的需求-供给，多余的可以向上传递，最后判断根节点正负即可。
#include
#include
using namespace std;
const int N=500005,M=500005;
struct edge{
int to,next;
} e[M];
int n,cnt,head[N],rin[N],maxv=-1,l,r,f[N];
void add(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int now,int bef,int k){
f[now]=rin[now]-k;
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (v==bef) continue;
dfs(v,now,k);
f[now]+=max(0,f[v]);
}
}
bool check(int k){
dfs(1,0,k);
if (f[1]<=0) return true;//!!!!!不是等于0!!!!!
else return false;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for (int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
add(u,v),add(v,u);
rin[u]++,rin[v]++;
}
for (int i=2;i<=n;i++)
rin[i]--;
l=0,r=n;
while (l<=r){
int mid=(l+r)/2;
if (check(mid)) r=mid-1;
else l=mid+1;
}
cout< CF296B Yaroslav and Two Strings
阴间题,大力转移要转一页纸(不愧是CF).
一遍就A了(主要在于样例真是强),把dp数组小的维放前面就比rk2快一倍(再写个取模优化是不是要快114514倍
题意:给定两个由数字和问号组成的等长字符串\(A,B\),定义性质\(P:\exist 1 \le i,j \le len\),满足\(A_i < B_i \and A_j > B_j\),求将问号替换成数字使\(A,B\)满足性质\(P\)的方案数.
考虑序列dp,观察到性质是两方面的,一方面是令A中有数大于B,另一方面则是小于,这两方面显然不能在一次转移中完成,故在状态设计中加入两维,分别记录是否已满足这两方面性质,再加一维表示序列的前i个,即用\(dp_{0/1,0/1,i}\)存储方案数.
考虑转移,由于不可能一次满足两个性质,显然满足一个性质的要从不满足任何性质和满足同一性质转移过来,而满足两个性质的要从两种满足一个性质和已经满足两个性质的转移过来,不满足任何性质的只能从之前不满足任何性质的转移过来,同时注意根据问号数量讨论:若都不是问号,根据数字大小关系直接转移;若有一个问号,考虑在满足给定性质时问号的方案数,显然种类并不多,可以提前算出.易得转移方程:
\[dp_{i,0,0}=\left\{ \begin{array}{rcl} dp_{i-1,0,0},D(A_i) \or D(B_i) \\ 10dp_{i-1,0,0},!D(A_i)\and !D(B_i) \end{array} \right. \\ dp_{i,0,1}=\left\{ \begin{array}{rcl} dp_{i-1,0,1},A_i=B_i\\ dp_{i-1,0,0}+dp_{i-1,0,1},A_i//写转移时始终想着一次最多只能满足一方面性质就会好写很多
#include
#include
using namespace std;
const int N=100005,Mod=1000000007;
int n,a[N],b[N];
long long dp[2][2][N];
string s1,s2;
int main() {
ios::sync_with_stdio(false);
cin>>n>>s1>>s2;
s1=' '+s1,s2=' '+s2;//让下标从1开始
for (int i=1; i<=n; i++) {
if (s1[i]=='?')a[i]=-1;//问号标为-1
else a[i]=s1[i]-'0';
if (s2[i]=='?')b[i]=-1;
else b[i]=s2[i]-'0';
}
dp[0][0][0]=1;
for (int i=1; i<=n; i++) {
if (a[i]!=-1&&b[i]!=-1) {
if (a[i]==b[i]) {//直接转移
dp[0][0][i]=dp[0][0][i-1]%Mod;
dp[0][1][i]=dp[0][1][i-1]%Mod;
dp[1][0][i]=dp[1][0][i-1]%Mod;
dp[1][1][i]=dp[1][1][i-1]%Mod;
}
if (a[i]>b[i]) {//只能满足一方面性质
dp[1][0][i]=dp[0][0][i-1]%Mod+dp[1][0][i-1]%Mod;
dp[1][1][i]=dp[0][1][i-1]%Mod+dp[1][1][i-1]%Mod;
}
if (a[i] @uptracer 写的更为巧妙:大大减小了转移的难度。
#include
using namespace std;
using ll=long long;
const int N=100010,mod=1e9+7;
int n;
char s[N],w[N];
ll solve(char *s,char *w)// s[i]<=w[i]
{
ll ans=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='?'&&w[i]=='?') ans=ans*55%mod;
else if(s[i]=='?'&&w[i]!='?') ans=ans*(w[i]-'0'+1)%mod;
else if(s[i]!='?'&&w[i]=='?') ans=ans*(10+'0'-s[i])%mod;
else if(s[i]>w[i]) return 0;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n;
cin>>s+1>>w+1;
ll ans=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='?') ans=ans*10%mod;
if(w[i]=='?') ans=ans*10%mod;
}
ans=((ans-solve(s,w)-solve(w,s))%mod+mod)%mod;
ll ret=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='?'&&w[i]=='?') ret=ret*10%mod;
else if(s[i]!=w[i]&&(s[i]!='?'&&w[i]!='?')) ret=0;
}
//cout< CF44E Anfisa the Monkey
给定一个字符串，要求将它分为k行长度>=a且<=b的段，输出这些被划分出来的部分，没有符合要求的划分就输出"No solution"
做法多种，比较随意，看代码即可。
#include
#include
using namespace std;
string s;
int k,a,b,head;
int main() {
ios::sync_with_stdio(false);
cin>>k>>a>>b;
cin>>s;
int l=s.length();
if (lb*k) {
cout<<"No solution"< P2986 [USACO10MAR]Great Cow Gathering G:
换根dp模板题.
题意:一棵树有点权和边权,求一个点使其他点到这个点的路径长乘以点权之和最小.解法:第一遍dfs求出以1为根节点的答案和每个子树的大小,第二次dfs换根,每次将移远根的和移近根用子树大小快速统计.转移方程:
\[dp_{v}=dp_{u}-size_v*dis_{u,v}+(Sum-size_v)*dis_{u,v} \]#include
#include
#define int long long
using namespace std;
const int N = 500005, M = 500005, INF = 1000000000000000000;
int n, head[N], cnt, tot, c[N], dis[N], ans = INF, siz[N], f[N], sum;
struct edge
{
int to, nxt, dis;
} e[M];
void add(int u, int v, int d)
{
e[++cnt].to = v;
e[cnt].nxt = head[u];
e[cnt].dis = d;
head[u] = cnt;
}
void dfs1(int k, int bef, int d)
{
siz[k] += c[k];
for (int i = head[k]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == bef)
continue;
dis[v] = c[v] * (d + e[i].dis);
tot += dis[v];
dfs1(v, k, d + e[i].dis);
siz[k] += siz[v];
}
}
void dfs2(int k, int bef)
{
for (int i = head[k]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == bef)
continue;
f[v] = f[k] - siz[v] * e[i].dis + (sum - siz[v]) * e[i].dis;
dfs2(v, k);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> c[i];
sum += c[i];
}
for (int i = 1; i <= n - 1; i++)
{
int u, v, d;
cin >> u >> v >> d;
add(u, v, d), add(v, u, d);
}
dfs1(1, 0, 0);
f[1] = tot;
dfs2(1, 0);
for (int i = 1; i <= n; i++)
ans = min(ans, f[i]);
cout << ans << endl;
}
一个题单codeforces 2000左右的dp题
CF148E Porcelain(想出部分）
- 好题,
完美诠释dp圣经.题意:有n个由正数组成的序列,取m次,每次只能从两端取,使总和最大.直接两维dp难以着手,考虑一种想法: - 发现对于每一个序列,取固定次数能获得最大价值是固定的,显然可以先预处理出结果,然后问题转化为:
- 1)有一个序列只能从两端取,求取k次的最大价值;容易发现LRLR和LLRR是等效的,即我们不关心取的顺序,只关心最终在左右分别取了多少个,先求出前缀和,然后枚举即可.
- 2)有n组物品,每组物品只能选一个,物品有价值和体积,求在给定体积下的最大价值.这里的“一组物品”指的是将同一序列中取法的取的次数作为体积,取得的价值作为价值形成的一个组,显然这个组中物品只能选一个.运用分组背包模板即可解决.
- 解决此题的难点在于需要发现在序列间选择和在序列内选择是独立的,从而防止无用的大量状态转移.
- 然而WA飞了....因为每个序列不一样长,所以使用偷懒的后缀和就没了....以后还是至少清一下len+1位置的数组...
//VSCode的格式化怎么这么难看...要不是有某二次元主题早就换了
#include
#include
#include
using namespace std;
const int N = 105, M = 10005;
int n, m;
int k[N], a[N], sum1[N], sum2[N], sub[N][N], dp[N][M];
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
memset(sum1, 0, sizeof(sum1));
memset(sum2, 0, sizeof(sum2));
cin >> k[i];
for (int j = 1; j <= k[i]; j++)
cin >> a[j];
for (int j = 1; j <= k[i]; j++)
sum1[j] = sum1[j - 1] + a[j];
for (int j = k[i]; j >= 1; j--)
sum2[j] = sum2[j + 1] + a[j];
for (int t = 1; t <= k[i]; t++)
for (int l = 0; l <= t; l++)
sub[i][t] = max(sub[i][t], sum1[l] + sum2[k[i] - (t - l) + 1]);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int t = 0; t <= min(j, k[i]); t++) //j要大于等于t
dp[i][j] = max(dp[i][j], dp[i - 1][j - t] + sub[i][t]);
cout << dp[n][m] << endl;
}
CF847E Packmen:(自己做出)
-
奇怪的东西
- WA了两小时
- 比rk2快一倍,但代码长4倍
请思考本题用dp怎么做
-
题意
今有一区间,人,物具陈其上,间或亦有空.其人可左右徙于上.求让人的移动轨迹覆盖所有物品的情况下,人移动的路程的最大值的最小值. -
题解
根据题意,显然看出是二分.再考虑一个人的走法:
-
向左走,不回头
-
向右走,不回头
-
向左再向右,左边重复走
-
向右再向左,右边重复走
-
若我们从左到右把人扫一遍,必然要保证先把左边的没走到的物品走到,同时在还有步数的情况下向右走.
这样会WA on #7 ,原因在于先向右走再向左走到第一个没走到的物品可能更优,因为重复的部分可能更少.
考虑分类讨论:用一个物品指针指向还没走到的最靠左的物品
-
步数不够到达最左边的没走到的物品\(\to\)直接
return false -
步数只能到最左边的物品,无法向右走\(\to\)把物品指针向右更新到人右边
-
步数很充足\(\to\)在3,4两种走法中取最优解
-
指针在人右边\(\to\)把物品指针尽可能向右更新
结束后判断指针是否大于\(Cnt_{package}\)即可
这样就又WA了,原因在于二分的右边界应当是\(\frac{3n}{2}\),即只有一个人在正中间,先向某方向然后再折返的答案,程序里为了简单写成了\(2n\).
最终复杂度:\(O(Cnt_{people}\log2n)\),明显快于\(O(n\log2n)\).
-
代码
#include
#include
using namespace std;
const int N = 100005;
int n, L, R, cnt1, cnt2;
int peo[N], pack[N];
string s;
bool check(int k)
{
int await_pick = 1;
for (int i = 1; i <= cnt1; i++)
{
int start_pos = await_pick;
if (await_pick > cnt2)
return true;
if (pack[start_pos] < peo[i])
{
if (pack[start_pos] < peo[i] - k)//第一种情况
return false;
if (k <= peo[i] - pack[start_pos] + 1)//第二种情况
{
while (pack[await_pick + 1] <= peo[i] && await_pick <= cnt2 && pack[await_pick + 1] <= peo[i + 1])
await_pick++;
if (pack[await_pick] <= peo[i] && pack[await_pick] <= peo[i + 1])
await_pick++;
}
else
{
if (k > (2 * (peo[i] - pack[start_pos])))
{//第三种情况,先向左走
int temp = k - (2 * (peo[i] - pack[start_pos]));
while (pack[await_pick + 1] <= peo[i] + temp && await_pick <= cnt2 && pack[await_pick + 1] <= peo[i + 1])
await_pick++;
if (pack[await_pick] <= peo[i] + temp && pack[await_pick] <= peo[i + 1])
await_pick++;
}
if (peo[i] + (k + pack[start_pos] - peo[i]) / 2 >= pack[await_pick])
{//第三种情况,先向右走
int temp = (k + pack[start_pos] - peo[i]) / 2;
while (pack[await_pick + 1] <= peo[i] + temp && await_pick <= cnt2 && pack[await_pick + 1] <= peo[i + 1])
await_pick++;
if (pack[await_pick] <= peo[i] + temp && pack[await_pick] <= peo[i + 1])
await_pick++;
}
}
}
else
{//第四种情况
while (pack[await_pick + 1] <= peo[i] + k && await_pick <= cnt2 && pack[await_pick + 1] <= peo[i + 1])
await_pick++;
if (pack[await_pick] <= peo[i] + k && await_pick <= cnt2 && pack[await_pick] <= peo[i + 1])
await_pick++;
}
}
if (await_pick > cnt2)
return true;
else
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> s;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == 'P')
peo[++cnt1] = i + 1;
if (s[i] == '*')
pack[++cnt2] = i + 1;
}
peo[cnt1 + 1] = 0x7fffffff;
pack[cnt2 + 1] = 0x7fffffff;
L = 1, R = 2 * n;//注意二分边界
while (L <= R)
{
int mid = (L + R) / 2;
if (check(mid))
R = mid - 1;
else
L = mid + 1;
}
cout << L;
}
CF1158C Permutation recovery(想到法1)
对于一个排列\(a1...an\), \(next_i\)表示排列中i后面第一个比\(ai\)大的位置.现给定一个排列的一部分\(next_i\)数组,试据此构造一个排列.
若\(next_i=n+1\)表示i后面没有比它更大的数,\(next_i=-1\)表示不确定.\(n \leq 5*10^5\)
法1: \(O(nlogn)\)
考虑定义,对于任意一个\(nexti\)不等于-1的位置i,有\(ai>aj(i+1\leq j \leq nexti-1),a_{next_i} > a_i\)成立,显然连边+拓扑排序,用线段树优化连边做到\(O(nlogn)\)即可.
法2: \(O(n)\)
- Step1 考虑没有-1,且next互不相同怎么做.由于交叉必然无解,所以形成的区间是这样的:
容易发现,如果next互不相同,我们按照\(next\)从大到小排序依次填数,方案必定是合法的,原因在于,一个位置有比另一个位置小的限制,当且仅当被一个\((i,next_i)\)的区间覆盖,排序后就保证了右边的比左边小,所以必然合法.
-
Step2 考虑有\(next\)相同怎么做.显然,对于\(next\)相等的位置,越靠前,数越大,对于这些位置按照从小到大排序即可.
-
Step3考虑有-1怎么做.相当于在不考虑-1形成的区间中加入许多新区间,使其合法,如图:
容易发现,只要让i直接指向i+1就不会产生任何交叉区间.如图:
用一个vector存储某个位置作为\(next\)被哪些点指向,扫一遍,依次填数,就是一种合法方案.
P5025 [SNOI2017]炸弹(学习了新算法)
在数轴上给定n个炸弹,每个炸弹有位置和爆炸半径,如果爆炸半径内有别的炸弹,那么爆炸时就会引爆它们,依次求出从某个炸弹起爆会引起多少个炸弹爆炸.\(n \leq 5*10^5\)
容易发现,本题与之前的CF1158C异曲同工.只是本题更为直观.
考虑二分查找出每个炸弹起爆能引发的爆炸区间,从该炸弹向引爆的炸弹连边,最后dfs过程中统计能到达的结点中最左和最右在哪即可.
由于n较大,连边复杂度过高,考虑线段树优化连边.显然连边之后,对于每个强联通分量,引爆其中任何一个都是引爆整个强联通分量,使用tarjan在线段树上缩点建新图,在新图上跑dfs即可.
思维难度不大,注意代码细节即可:
-
初始化不能只到n,原因在于线段树缩点后点数可能依然多于原图(卡了半天).
-
数字较大,注意long long 和取模.
-
dfs时注意一次性从前后更新所有经过的结点,而不是依次dfs,那样复杂度就boom了
#include#include #include #include
「Wdoi2021」Windy OI Codeforces Round 1
T1 Beautiful Array
题意:试将一个长度为 n的括号串分为 2m个子序列，子序列可以为空，且每个字符都必须分到恰好一个子序列中。使得至少 m个子序列为匹配的括号串。空序列不算匹配的括号序列。无解请输出 0，否则输出 1。本题多组数据，其中数据组数为 T。定义 A为 B的子序列当且仅当 A 能由 B 在顺序不改变的前提下删除若干元素后得到。\(1\leq T,n,m \leq 200\)
签到题.由于数据非常小,暴力求出可能匹配的括号串与m比较即可.
#include
#include
using namespace std;
const int N = 250;
int T, n, m;
string s;
int vis[N];
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
cin >> s;
s = ' ' + s;
for (int i = 1; i <= n; i++)
vis[i] = 0;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
if (vis[i])
continue;
if (s[i] == '(')
for (int j = i + 1; j <= n; j++)
if (s[j] == ')' && !vis[j])
{
vis[i] = 1, vis[j] = 1, cnt++;
break;
}
if (s[i] == ')')
for (int j = 1; j <= i - 1; j++)
if (s[j] == '(' && !vis[j])
{
vis[i] = 1, vis[j] = 1, cnt++;
break;
}
}
if (cnt >= m)
cout << 1 << endl;
else
cout << 0 << endl;
}
}
T2 Alice Wins! (easy version)
AB 每队 2n人正在玩石头剪刀布。A 队第 \(i\) 个人出$ a_i$，B 队第 \(i\) 人出 \(b_i\).编号相同的人会对战。若 A 队赢则加一分，平不得分，输扣一分。你可以至多改变每队 \(n\) 个人的出拳方案，使得 A 队的得分最高。输出得分的最大值和任意一组构造方案。
本题中，我们用 1代表石头，2代表剪刀，3代表布。
签到题.容易发现最坏情况也只需要一边各n次就能改成全赢,所以扫一遍直接改成全赢即可.注意不要让某一边改的次数超过n.
#include
#include
using namespace std;
const int N = 500005;
int n;
int cmp(int a, int b)
{
if (a == b)
return 0;
if (a != 1 && b != 1)
{
if (a < b)
return 1;
if (a > b)
return -1;
}
if (a == 1)
{
if (b == 2)
return 1;
if (b == 3)
return -1;
}
if (b == 1)
{
if (a == 2)
return -1;
if (a == 3)
return 1;
}
}
int a[N], b[N];
int cnt;
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= 2 * n; i++)
cin >> a[i];
for (int i = 1; i <= 2 * n; i++)
cin >> b[i];
cnt = 0;
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == -1 && cnt < n)
{
cnt++, a[i]++;
if (a[i] == 4)
a[i] = 1;
}
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == 0 && cnt < n)
{
cnt++, a[i]--;
if (a[i] == 0)
a[i] = 3;
}
cnt = 0;
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == -1 && cnt < n)
{
cnt++, b[i]--;
if (b[i] == 0)
b[i] = 3;
}
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == 0 && cnt < n)
{
cnt++, b[i]++;
if (b[i] == 4)
b[i] = 1;
}
int sum = 0;
for (int i = 1; i <= 2 * n; i++)
sum += cmp(a[i], b[i]);
cout << sum << endl;
for (int i = 1; i <= 2 * n; i++)
cout << a[i] << " ";
cout << endl;
for (int i = 1; i <= 2 * n; i++)
cout << b[i] << " ";
cout << endl;
}
}
T3 Alice Wins! (hard version)
题意:同T2,但改为每边改恰好n次.
略加思考容易发现,我们只需要解决改完全赢之后如何浪费次数就可以了.显然对于没改过的,即本来就赢的位置,可以上下同时+1/-1浪费两次操作,这样可能会因为奇偶剩下两边中某一边的一次修改,只需要将之前改成赢的的位置从改一边变成赢变成改两边变成赢即可.
码量较大细节较多,但没有太大难度.
#include
#include
#include
using namespace std;
const int N = 500005;
int n;
int cmp(int a, int b)
{
if (a == b)
return 0;
if (a != 1 && b != 1)
{
if (a < b)
return 1;
if (a > b)
return -1;
}
if (a == 1)
{
if (b == 2)
return 1;
if (b == 3)
return -1;
}
if (b == 1)
{
if (a == 2)
return -1;
if (a == 3)
return 1;
}
}
int a[N], b[N], arta[N], artb[N], ta[N], tb[N];
int cnta, cntb, cntfail, cntdraw;
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
cin >> n;
cntdraw = 0, cntfail = 0, cnta = 0, cntb = 0;
for (int i = 1; i <= 2 * n; i++)
arta[i] = 0, artb[i] = 0;
for (int i = 1; i <= 2 * n; i++)
{
cin >> a[i];
ta[i] = a[i];
}
for (int i = 1; i <= 2 * n; i++)
{
cin >> b[i];
tb[i] = b[i];
}
for (int i = 1; i <= 2 * n; i++)
{
if (cmp(a[i], b[i]) == -1)
cntfail++;
if (cmp(a[i], b[i]) == 0)
cntdraw++;
}
if (cntfail % 2 == 1)
cntfail++;
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == -1 && cnta < cntfail / 2)
{
cnta++;
a[i]++;
if (a[i] == 4)
a[i] = 1;
arta[i] = 1;
}
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == -1 && cntb < cntfail / 2)
{
cntb++;
b[i]--;
if (b[i] == 0)
b[i] = 3;
artb[i] = 1;
}
int sa = cnta, sb = cntb;
if (cntdraw % 2 == 1)
cntdraw++;
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == 0 && cntb - sb < cntdraw / 2)
{
cntb++;
b[i]++;
if (b[i] == 4)
b[i] = 1;
artb[i] = 1;
}
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == 0 && cnta - sa < cntdraw / 2)
{
cnta++;
a[i]--;
if (a[i] == 0)
a[i] = 3;
arta[i] = 1;
}
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == 1 && !(arta[i] || artb[i]) && cnta < n && cntb < n)
{
cnta++, cntb++;
a[i]++, b[i]++;
if (a[i] == 4)
a[i] = 1;
if (b[i] == 4)
b[i] = 1;
}
if (cnta != n)
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == 1 && artb[i] && cnta < n)
{
cnta++;
a[i]++, b[i]++;
if (a[i] == 4)
a[i] = 1;
if (b[i] == 4)
b[i] = 1;
if (b[i] == tb[i])
{
a[i]++, b[i]++;
if (a[i] == 4)
a[i] = 1;
if (b[i] == 4)
b[i] = 1;
}
break;
}
if (cntb != n)
for (int i = 1; i <= 2 * n; i++)
if (cmp(a[i], b[i]) == 1 && arta[i] && cntb < n)
{
cntb++;
a[i]++, b[i]++;
if (a[i] == 4)
a[i] = 1;
if (b[i] == 4)
b[i] = 1;
if (a[i] == ta[i])
{
a[i]++, b[i]++;
if (a[i] == 4)
a[i] = 1;
if (b[i] == 4)
b[i] = 1;
}
break;
}
assert(cnta == n && cntb == n);
int sum = 0;
for (int i = 1; i <= 2 * n; i++)
sum += cmp(a[i], b[i]);
cout << sum << endl;
for (int i = 1; i <= 2 * n; i++)
cout << a[i] << " ";
cout << endl;
for (int i = 1; i <= 2 * n; i++)
cout << b[i] << " ";
cout << endl;
}
}
T4 Magical Expression
给定一个合法的含 |&?01 的后缀表达式（以字符串形式给出，其为“合法的”代表将所有 ? 替换为运算符后其会成为一个合法的后缀表达式），试求出其有多少个子串满足：
- 将所有的
?替换成|或&后，该串为合法的后缀表达式； - 存在一种将所有的
?替换成|或&的方法使得该式所得结果为 0，同时也存在替换方法使得结果为 1。
请输出这样的子串的数量。两个子串是不同的仅当它们长度不同或位置不同。
比T3还要签到的一道题,但细节也比较多,最终也没能调出来.
总结
本场比赛码量较大,难度不大,但由于码力太差只切掉了三个题,luogu仅排到rk204,主要问题在于:
- T1没有注意到数据范围是钦定暴力做法,想了较长时间没有必要的优化.
- T2没有一遍AC.
- T3一开始想的是把赢改为平.
- T4这一类的表达式题写的不熟练.
CF549B Looksery Party(看了题解)
给定一张\(n\)个点的有向图,不一定联通,每个点都有一个自环.对于每个点\(i\)给出\(a_i\),试构造一种选点方案使得每个点的入度都不等于\(a_i\).
容易发现,对于\(a_i=0\)的点,我们必须将它们选进去.选入之后我们将该点所指向的点\(a_i\)减1,实际上相当于比较方便地统计当前选点产生的对其他点的入度.每次选出\(a_i=0\)的点,重复上述操作,正确性显然.同时也说明并不存在无解的情况.
#include
#include
#include
using namespace std;
const int N = 105;
struct edge
{
int to, next;
} e[N * N];
int cnt, head[N];
void add(int u, int v)
{
e[++cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
int n;
int a[N], p[N], ans;
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
for (int j = 0; j < s.length(); j++)
if (s[j] == '1')
add(i, j + 1);
}
for (int i = 1; i <= n; i++)
cin >> a[i];
while (1)
{
bool flag = false;
for (int i = 1; i <= n; i++)
if (a[i] == 0 && !p[i])
{
ans++;
p[i] = 1;
flag = true;
for (int j = head[i]; j; j = e[j].next)
a[e[j].to]--;
break;
}
if (!flag)
break;
}
cout << ans << endl;
for (int i = 1; i <= n; i++)
if (p[i])
cout << i << " ";
cout << endl;
}
CF525D Arthur and Walls(写的是错解)
给出\(n \times m\)?的矩阵,有*,.两种符号,要求将最少的*变成.让所有.的连通块变为矩形.
法1:乱搞:
搜一遍记录每个连通块的端点,将其视为矩形,用扫描线合并相交的矩形.不保证能过.
法2:反向乱搞:
从每个*搜,看周围是否被连续的一个拐角形.包围,若是则修改.复杂度比较优秀.
莫名其妙C++17会爆栈.
#include
#include
#include
using namespace std;
char map[2021][2021];
int n, m;
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, -1, 1, 1, -1};
void dfs(int x, int y)
{
if (x-1<0||y-1<0)
return;
assert(x<=2000&&y<=2000);
if ((map[x + 1][y] == '.' && map[x][y + 1] == '.' && map[x + 1][y + 1] == '.') || (map[x + 1][y] == '.' && map[x][y - 1] == '.' && map[x + 1][y - 1] == '.') || (map[x - 1][y] == '.' && map[x][y + 1] == '.' && map[x - 1][y + 1] == '.') || (map[x - 1][y] == '.' && map[x][y - 1] == '.' && map[x - 1][y - 1] == '.'))
{
map[x][y] = '.';
for (int i = 0; i <= 7; i++)
{
int tx = x + dx[i], ty = y + dy[i];
if (tx > n || tx < 1 || ty > m || ty < 1)
continue;
if (map[tx][ty] == '.')
continue;
dfs(x + dx[i], y + dy[i]);
}
}
}
int main()
{
//freopen("1.in", "r", stdin);
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> map[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (map[i][j] == '*')
dfs(i, j);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
cout << map[i][j];
cout << endl;
}
return 0;
}
CF1051F The Shortest Statement(自己做出)
给定一个树，在树上加k条边，求全源最短路。(\(n \le 10^5 \space, k \le 20\))
显然利用树的性质，考虑如何处理加的20条边即可。可以枚举所有经过的非树边，对每个非树边的端点依次更新答案，再结合树上路径长度即可。
最小生成树+lca+dij即可解决的一道紫题...
写的时候要注意不同的图、树的混淆问题。
把lca板子写错调了一小时？？？ 有时候对树上深度总有种从下到上的错觉。
#include
#include
#include
#include
#include
#include
#include P3390 【模板】矩阵快速幂
只是模板而已。
但是没注意到输入都要开long long，还是WA+T了几次。以后还是在不MLE的情况下全开long long，省的乱七八糟的事。
#include
#include
#include
using namespace std;
const int N=105;
const int Mod=1000000007;
int n;
long long t;
struct martix {
long long fac[N][N];
martix() {
memset(fac,0,sizeof(fac));
}
void build() {
for (int i=1; i<=n; i++)
fac[i][i]=1;
}
} Ans,Base;
martix operator *(const martix &A,const martix &B) {
martix temp;
for (int k=1; k<=n; k++)
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
temp.fac[i][j]=(temp.fac[i][j]+A.fac[i][k]*B.fac[k][j]%Mod)%Mod;
return temp;
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>t;
Ans.build();
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
cin>>Base.fac[i][j];
while (t>0) {
if (t&1)
Ans=Ans*Base;
Base=Base*Base;
t>>=1;
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++)
cout< CF543B Destroying Roads(没有考虑到分类讨论)
边权全为1的无向连通图,最大化不在s1到t1,s2到t2两条路径上的边数.\(n \le 3000\)
直接最短路明显是错的,因为将两路径重合部分计算了两次.由于n只有3000,可以先求出全源最短路(别nt用floyd),然后枚举重合部分的左右端点,注意s1,s2可能同侧或依次,分类讨论两种情况即可.
#include
#include
#include
using namespace std;
const int N = 3005, M = 3005 * 3005, INF = 0x3f3f3f3f;
int read()
{
int f = 1, x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int n, m, s1, t1, l1, s2, t2, l2, ans = -1;
int dis[N][N];
int cnt, head[N];
struct edge
{
int to, next;
} e[M];
void add(int u, int v)
{
e[++cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
void bfs(int s)
{
queue q;
while (!q.empty())
q.pop();
dis[s][s] = 0;
q.push(s);
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i = head[x]; i; i = e[i].next)
{
int v = e[i].to;
if (dis[s][v] != INF)
continue;
dis[s][v] = dis[s][x] + 1;
q.push(v);
}
}
}
int main()
{
n = read(), m = read();
for (int i = 1; i <= m; i++)
{
int u = read(), v = read();
add(u, v), add(v, u);
}
cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = INF;
for (int i = 1; i <= n; i++)
bfs(i);
if (dis[s1][t1] <= l1 && dis[s2][t2] <= l2)
ans = max(ans, m - dis[s1][t1] - dis[s2][t2]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 && dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)
ans = max(ans, m - dis[s1][i] - dis[j][t1] - dis[s2][i] - dis[j][t2] - dis[i][j]);
if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 && dis[t2][i] + dis[i][j] + dis[j][s2] <= l2)
ans = max(ans, m - dis[s1][i] - dis[j][t1] - dis[t2][i] - dis[j][s2] - dis[i][j]);
}
cout << ans << endl;
}
P4551 最长异或路径(模板题)
给一棵边带权的树,求一条路径使得路径上所有边的异或最大.
容易发现abb=a,所以可以将两条重合的异或路径合并而不影响结果.考虑求出从根节点到每个节点的异或值,将这些值放进0/1trie树里,从高位贪心即可.
注意:根据讨论结果,还是将初始tot和now赋成1比较好,并且中间变量要取成bool型.
#include
#include
using namespace std;
const int N = 100005;
int n, tot;
int val[N];
int cnt, head[N];
struct edge
{
int from, to, next, d;
} e[N * 2];
int tree[N << 5][2];
void add(int u, int v, int d)
{
e[++cnt].to = v;
e[cnt].from = u;
e[cnt].next = head[u];
e[cnt].d = d;
head[u] = cnt;
}
void build(int k, int bef)
{
for (int i = head[k]; i; i = e[i].next)
{
int v = e[i].to;
if (v == bef)
continue;
val[v] = val[k] ^ e[i].d; //把根节点到每个节点的路径异或求出来
build(v, k);
}
}
void addtree(int v)
{
int now = 0;
for (int i = (1 << 30); i; i >>= 1)
{
bool temp = v & i; //将每一位取出来
if (!tree[now][temp])
tree[now][temp] = ++tot; //将now的左右结点加入并编号,显然应当编一次号
now = tree[now][temp]; //迭代到对于插入的v的i位对应的结点
}
}
int query(int v)
{
int ans = 0, now = 0;
for (int i = (1 << 30); i; i >>= 1)
{
bool temp = v & i;
if (tree[now][temp ^ 1]) //如果trie树上存在与第i位0/1不同的结点,就选,否则不得不算等于0的点
{ //显然从高位到低位贪心即可.
ans = (ans << 1) | (temp ^ 1);
now = tree[now][temp ^ 1]; //迭代到下一节点
}
else
{
ans = (ans << 1) | temp;
now = tree[now][temp]; //迭代到下一节点
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n - 1; i++)
{
int u, v, d;
cin >> u >> v >> d;
add(u, v, d);
add(v, u, d);
}
build(1, 0);
for (int i = 1; i <= n; i++)
addtree(val[i]);
int maxn = 0;
for (int i = 1; i <= n; i++)
maxn = max(maxn, query(val[i]) ^ val[i]);
cout << maxn << endl;
}
CF817E Choosing The Commander(想到正解但未写对)
有Q次操作，每次操作有三种类型，分别是
1 pi 把 pi 加入集合 S
2 pi 把 pi 从集合 S 中删除
3 pi li 表示查询集合中有多少个元素异或上 pi 后 小于 li
0/1trie树.显然对于每一位,若这一位异或后比li的这一位小,那么该结点所在的子树异或后都必然小于li,而若与li的这一位相等,则向这边迭代.
#include
#include
using namespace std;
const int N = 3000005;
int n, tot = 1;
int val[N], tree[N][2];
void add(int k, int v)
{
int now = 1;
for (int i = (1 << 30); i; i >>= 1)
{
val[now] += v;
bool temp = k & i;
if (!tree[now][temp])
tree[now][temp] = ++tot;
now = tree[now][temp];
}
val[now] += v;
}
int query(int v, int l)
{
int now = 1, ans = 0;
for (int i = (1 << 30); i; i >>= 1)
{
bool temp1 = v & i, temp2 = l & i;
if (temp1 < temp2)
ans += val[tree[now][0]];
if (temp1 && temp2)
ans += val[tree[now][1]];
if (temp2)
now = tree[now][temp1 ^ 1];
else
now = tree[now][temp1];
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (x == 1)
{
int v;
cin >> v;
add(v, 1);
}
if (x == 2)
{
int v;
cin >> v;
add(v, -1);
}
if (x == 3)
{
int v, l;
cin >> v >> l;
cout << query(v, l) << endl;
}
}
}
CF768E Game of Stones(看了题解)
有n堆石子,对于任意一堆,取的个数不能与之前任何一次取这堆取的个数相同.两人轮流取,问先手是否必胜.
显然对于任意一堆石子,取的次数最多的方案是从1开始依次递增取(最后若有剩余就合并到最后一次取的中去),比这种方案取的次数少的方案显然都是成立的,由于我们只关心某堆石子到底取多少次,显然转化为NIM游戏(因为NIM游戏就是每堆石子存在取1-n次取完的方案,容易发现,这与本问题是一致的,因为石子在影响胜负这个问题上的本质是其取的次数方案而不是他它的个数,即由个数和取法共同决定的.)将所有次数异或起来即为结果.
解题关键在于认识到NIM游戏的本质.
#include
#include
using namespace std;
int n, ans, temp, sum;
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
{
temp = 0, sum = 0;
cin >> temp;
for (int i = 1;; i++)
{
sum += i;
if (sum == temp)
{
temp = i;
break;
}
if (sum > temp)
{
temp = i - 1;
break;
}
}
ans ^= temp;
}
if (ans)
cout << "NO" << endl;
else
cout << "YES" << endl;
}
CF940E Cashback(想出结论,但没想到dp)
给出一个长度为n的序列,和整数c.将其划分为任意段.对于每段,去掉前\(\frac{len}{c}\)(下取整)小的数,最小化剩下的数的和.
容易发现,对于小于c长度的段,不妨将其划分成长度为1,这样是等效的,且有利于最小化.对于长度大于2c的段,先把多出2c的部分拆成长度为1的段,然后把2c拆成两个c,这样一定不会变劣.原因在于较长段的最小和次小不可能比划分成两个较短段的最小值大.所以只有两种划分:长度为1,长度为c.(自己想到了这里)
考虑转移,容易发现如果选长度为1的段,会使答案直接多a_i,而选择长度为c的段,会使答案多sum-min,即区间和去掉一个最小值.用单调队列求出长度为c的所有段的最小值.转移即可.
还是要多注意单调队列写法.
#include
#include
#include
#define int long long
using namespace std;
const int N = 100005, INF = 0x7fffffff;
int n, c, head = 1, tail = 0;
int a[N], q[N], g[N], sum[N], f[N];
signed main()
{
ios::sync_with_stdio(false);
cin >> n >> c;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
for (int i = 1; i <= n; ++i)
{
while (head <= tail && q[head] + c <= i)
head++;
while (head <= tail && a[q[tail]] >= a[i])
tail--;
q[++tail] = i;
g[i] = a[q[head]];
}
for (int i = 1; i <= n; i++)
if (i >= c)
f[i] = min(f[i - 1] + a[i], f[i - c] + sum[i] - sum[i - c] - g[i]);
else
f[i] = f[i - 1] + a[i];
cout << f[n] << endl;
}
CF1584
A Mathematical Addition
给出 \(u,v\) , 求方程\(\frac{x}{u}+\frac{y}{v}=\frac{x+y}{u+v}\)的一组整数解.
暴力合并分数可得:
\[xv^2+yu^2=0 \]显然\(x=u^2,y=-v^2\)即可.注意防止爆int.
#include
#include
using namespace std;
int T;
long long a, b, x, y;
int main()
{
ios::sync_with_stdio(false);
cin >> T;
while (T--)
{
cin >> a >> b;
x = a * a, y = b * b;
cout << x << " " << -y << endl;
}
}
B Coloring Rectangles
给出一个\(n \times m\)的矩形.初始全是红色,将其任意横竖划分成小矩形(不能是\(1\times 1\)),再将一些色块染成蓝色,使没有一个矩形里相邻块颜色相同，任意划分，最小化必须染成蓝色的格子数.
由于任意划分,不妨尽量划分成\(1\times3\) 的块,保证一个蓝块覆盖两个红块.
注意竖直划分完之后还可以水平划分.
写的还是比较简洁的.
#include
#include
using namespace std;
long long T, n, m;
long long solve(long long r, long long c)
{
if (r == 1)
{
if (c % 3 == 0)
return c / 3;
else
return c / 3 + 1;
}
if (r == 2 && c == 2)
return 2;
if (r % 3 == 0)
return c * (r / 3);
else
return c * (r / 3) + solve(c, r % 3);
}
int main()
{
ios::sync_with_stdio(false);
cin >> T;
while (T--)
{
cin >> n >> m;
cout << min(solve(m, n), solve(n, m)) << endl;
}
}
C Two Arrays
给两个序列a,b,问能否通过一次如下操作把a变成b:
使a中任意个数+1,然后随意改变a的顺序.
想复杂了,以为是二分图,画了几个样例发现很符合,但估计过不去.
yyq云:排序
然后就没有然后了.
#include
#include
#include
using namespace std;
const int N = 105;
int T, n;
int a[N], b[N];
int main()
{
ios::sync_with_stdio(false);
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
bool flag = true;
for (int i = 1; i <= n; i++)
if (a[i] != b[i] && a[i] + 1 != b[i])
{
cout << "NO" << endl;
flag = false;
break;
}
if (flag)
cout << "YES" << endl;
}
}
D Guess the Permutation
长度为n的序列\(a\)一开始满足\(a_i=i\),已经经过下面一次操作:
选择\(i,j,k\),将\([i,j-1]\)取反,\([j,k]\)取反.
每次可以向交互库询问区间逆序对数,最多询问40次，确定i,j,k.(\(n\leq 10^9\))
考场上英语不好,读了半天读不下去了,去做E,发现不可做,就弃赛了.
总结
这次比赛ABC均为结论题(感觉后面也有点像,但我不会),其中B题较有新意.A,C应该属于送分题难度,但是C却想复杂了,最后开题顺序问题导致只做了三个题.排了rk2000/10000,不太理想.以后要对一些奇怪的结论敢于尝试,快速写出代码或者快速hack掉,不能在证明上浪费太多时间.另外要把握题目难度,防止误判.
CF1605
A A.M. Deviation
在三元组\(a1,a2,a3\)上定义d运算:\(d=\abs{a_1+a_3-2a_2}\).
可以做任意多次如下操作：
选择\(a1,a2,a3\)中两个数，将其分别+1和-1.
对于给定的\(a1,a2,a3\) ,最小化d 的值.
容易发现结果只可能是0/1,只与和有关.
#include
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
int T=0;
cin>>T;
while (T--){
int a=0,b=0,c=0;
cin>>a>>b>>c;
if ((a+b+c)%3==0)
cout<<0< B Reverse Sort
给定一个01串,每次进行如下操作:
选择串中任意个数,它们形成不升序列,将它们对称翻转.
问将原序列变为不降序列的最少操作数.输出方案.
容易发现最多也只需要一次翻转,只需要找到左边的1和右边的0一样多的位置翻转即可.
代码写的很丑...
#include
#include
using namespace std;
const int N=1005;
int cnt,tot,a[N],n;
char c;
bool flag;
int main(){
int T;
cin>>T;
while (T--){
cnt=0,tot=0,flag=true;
cin>>n;
for (int i=1;i<=n;i++){
cin>>c;
a[i]=c-'0';
if (a[i]==1) tot++;
if (i!=1&&a[i]==0&&a[i-1]==1) {
flag=false;
}
}
if (tot==0||tot==n||flag){
cout<<0<1;i--){
if (a[i]==1)
tot--;
else
cnt++;
if (tot==cnt){
cout< 总结
深夜打比赛,状态很差,仅做出两题,rk5000+,不太理想.
以后赛前要多睡觉.
支配(灭绝)树(P2597 [ZJOI2012]灾难)
支配树:满足树上任何一点的所有祖先都是他的支配点的树.
支配点:在图中指定一个起点s,若删去一个点t,s到w就没有路径,则t为w的支配点.
-
一棵树本身就是支配树
-
对于DAG:
- 在原图上拓扑排序.
- 按照拓扑序建支配树,方法是求出所有原图上有边指向该节点的点(即反图上该节点指向的点)的支配树上lca,将该节点设为lca的子结点,顺便更新深度,fa数组等信息.
- dfs求出每个点的子树size.
- 结果即为每个点子树(不含该点)的size.
-
对于一般图:
- 去问tarjan.
-
#include#include #include using namespace std; const int N = 100005; int n, x; int rin[N], head[3][N * 2], cnt[3], index[N], dep[N], fa[N][21], siz[N]; queue q; struct edge { int to, next; } e[3][N * 2]; void add(int u, int v, int type) { e[type][++cnt[type]].to = v; e[type][cnt[type]].next = head[type][u]; head[type][u] = cnt[type]; } void topo() { for (int i = 1; i <= n; i++) if (!rin[i]) q.push(i); int tot = 0; while (!q.empty()) { int x = q.front(); q.pop(); index[++tot] = x; for (int i = head[0][x]; i; i = e[0][i].next) { int v = e[0][i].to; rin[v]--; if (!rin[v]) q.push(v); } } } int lca(int a, int b) { if (dep[a] > dep[b]) swap(a, b); for (int i = 20; i >= 0; i--) if (dep[fa[b][i]] >= dep[a]) b = fa[b][i]; if (a == b) return a; for (int i = 20; i >= 0; i--) if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i]; return fa[a][0]; } void dfs(int k) { for (int i = head[2][k]; i; i = e[2][i].next) { int v = e[2][i].to; dfs(v); siz[k] += siz[v]; } siz[k]++; } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) { while (1) { cin >> x; if (x == 0) break; rin[i]++; add(x, i, 0); add(i, x, 1); } } topo(); for (int i = 1; i <= n; i++) { int ans = e[1][head[1][index[i]]].to; for (int j = head[1][index[i]]; j; j = e[1][j].next) ans = lca(ans, e[1][j].to); add(ans, index[i], 2); dep[index[i]] = dep[ans] + 1; fa[index[i]][0] = ans; for (int j = 1; j <= 20; j++) fa[index[i]][j] = fa[fa[index[i]][j - 1]][j - 1]; } dfs(0); for (int i = 1; i <= n; i++) cout << siz[i] - 1<
P5960 【模板】差分约束算法
给出m个不等式,每个不等式包含两个未知数和一个常数,求一组解或判定无解.
观察式子\(x_i-x_j \le c_k\) 不知道为什么就能观察出来它像最短路里的松弛操作.
所以建图,类比式子 \(dis_i \le dis_j + w_k\) ,容易发现最终解即为dis,有负环则无解(不知道原因.
#include
#include
using namespace std;
const int N=500005,M=500005,INF=0x7fffffff;
int n,m;
int dis[N];
struct edge{
int from,to,dis;
} e[M];
bool bellman_ford(int s){
for (int i=1;i<=n;i++) dis[i]=1e9;
dis[s]=0;
for (int t=1;t<=n;t++)
for (int i=1;i<=m;i++)
dis[e[i].to]=min(dis[e[i].to],dis[e[i].from]+e[i].dis);
for (int i=1;i<=m;i++)
if (dis[e[i].to]>dis[e[i].from]+e[i].dis)
return false;
return true;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for (int i=1;i<=m;i++)
cin>>e[i].to>>e[i].from>>e[i].dis;
if (bellman_ford(1))
for (int i=1;i<=n;i++)
cout< CF803E Roma and Pokar
给定一个由 W,D,L,? 构成的长度为 \(n\) 的字符串，并给定一个常数 \(k\)，你要替换字符串中的所有 ?，使得原串的 W,L 出现次数之差的绝对值为 \(k\)，且除原串外任意前缀的 W,L 出现次数之差的绝对值小于 \(k\)，求构造出的字符串，无解输出 NO，否则输出构造后的字符串。
法一:差分约束
将等于 \(k\) ,小于 \(k\) 全部转化为差分约束.跑一遍spfa得解。难写,没有优化空间。
法2:DP \(O(n^2)\)
设 \(dp_{i,j}\) 表示对于字符串前 \(i\) 位, W , L 出现次数绝对值为 \(j\) 是否有解。\(dp_{0,0}\) 显然初始化为 true .则有如下转移方程:(设四种字符依次为 \(1,0,-1,2\) )
显然枚举 \(j\) 的范围是 \((-k,k)\) ,注意不要像某些题解一样访问数组负下标。
另外开一个数组记录某状态是由哪一状态转移过来的即可。
#include
#include
#include **法3: DP **
考虑优化,首先容易发现所有为 true 的dp数组必然在给定的 \(i\) 上形成连续段。这是由于初始为真的只有一个位置,而之后的每次更新都只会向上\下\上下平移 \(1\) 格,所以必然形成连续段。这样,每次只需要从之前保存的 \(i-1\) 时为真的dp数组的左右端转移即可。这样就做到为 \(O(n)\) 的复杂度。
据说还有更快的栈+贪心做法...
代码来自 @mig
#include
using namespace std;
pair w[2006];
int main() {
int n, k;
bool flag = false;
string s;
cin>> n >> k;
cin>> s;
s = " " + s;
for(int i = 1; i < n; i++) {
if(s[i] == 'W') {
w[i-1].first + 1 < k ? w[i].first = w[i-1].first + 1 : flag = true;
w[i-1].second + 1 < k ? w[i].second = w[i-1].second + 1 : w[i].second = w[i-1].second;
} else if(s[i] == 'L') {
w[i-1].first - 1 > -k ? w[i].first = w[i-1].first - 1 : w[i].first = w[i-1].first;
w[i-1].second - 1 > -k ? w[i].second = w[i-1].second - 1 : flag = true;
} else if(s[i] == 'D')
w[i].first = w[i-1].first, w[i].second = w[i-1].second;
else {
w[i-1].second + 1 < k ? w[i].second = w[i-1].second + 1 : w[i].second = w[i-1].second;
w[i-1].first - 1 > -k ? w[i].first = w[i-1].first - 1 : w[i].first = w[i-1].first;
}
if(flag)
return 0*puts("NO");
}
if(s[n] == 'W') {
w[n].first = w[n-1].first + 1;
w[n].second = w[n-1].second + 1;
} else if(s[n] == 'L') {
w[n].first = w[n-1].first - 1;
w[n].second = w[n-1].second - 1;
} else if(s[n] == 'D') {
w[n].first = w[n-1].first;
w[n].second = w[n-1].second;
} else {
w[n].first = w[n-1].first - 1;
w[n].second = w[n-1].second + 1;
}
if(w[n].first > -k && w[n].second < k)
return 0*puts("NO");
int j;
w[n].second == k ? j = k : j = -k;
for(int i = n; i > 0; i--) {
char c = s[i];
if(c == 'W')
j--;
else if(c == 'L')
j++;
else if(c == '?') {
if(j - 1 >= w[i-1].first)
s[i] = 'W', j--;
else if(j + 1 <= w[i-1].second)
s[i] = 'L', j++;
else
s[i] = 'D';
}
}
cout<< s.substr(1, n);
return 0;
}
P7914 [CSP-S 2021] 括号序列
由于众所周知,题意略.
容易发现两维dp必死无疑.考虑将不同类型分开:
- 星
- 括号
- 括号星
- 星括号
- 括号星括号,括号括号,括号
- 星括号星,星
共六种.转移见代码.
#include
#include
using namespace std;
const int N=505;
const int MOD=1000000007;
int n,k;
long long dp[N][N][7];
string a;
/*
1: *************
2: ********(...)
3: (...)********
4: (...)***(...)
5: (...........)
6: ****(...)****
*/
int main() {
freopen("bracket.in","r",stdin);
ios::sync_with_stdio(false);
cin>>n>>k;
cin>>a;
a=' '+a;
for (int i=1; i<=n; i++)
dp[i][i-1][1]=1;//方便下面边界情况转移,即len较短减越位的情况.
for (int len=1; len<=n; len++) {
for (int s=1; s<=n-len+1; s++) {
int e=s+len-1;
if (len<=k&&(a[e]=='?'||a[e]=='*'))
dp[s][e][1]=dp[s][e-1][1];
if ((a[s]=='('||a[s]=='?')&&(a[e]==')'||a[e]=='?'))
dp[s][e][5]=(dp[s+1][e-1][1]+dp[s+1][e-1][2]+dp[s+1][e-1][3]+dp[s+1][e-1][4])%MOD;
//括号=(星+星括号+括号星+括号星括号+括号),括号匹配.
for (int k=s; k P2055 [ZJOI2009]假期的宿舍
二分图板子题,但莫名其妙很难写对.个人很反感这种用题意绕弯子来考人的题.
#include
#include
#include
using namespace std;
const int N=105;
int T,n,a,cnt,tot,sum;
int school[N],home[N],vis[N],p[N];
int head[N];
struct edge{
int to,next;
} e[N*N];
void add(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
bool match(int k) {
for (int i=head[k];i;i=e[i].next) {
int v=e[i].to;
if (vis[v]) continue;
vis[v]=1;
if (!p[v]||match(p[v])) {
p[v]=k;
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin>>T;
while (T--) {
cnt=0,tot=0,sum=0;
memset(head,0,sizeof(head));
memset(p,0,sizeof(p));
cin>>n;
for (int i=1; i<=n; i++)
cin>>school[i];
for (int i=1; i<=n; i++) {
cin>>home[i];
if (home[i]==0&&school[i])
add(i,i);
}
for (int i=1; i<=n; i++)
if (!school[i]||(school[i]&&!home[i]))
++tot;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) {
cin>>a;
if (a&&school[j])
add(i,j);
}
for (int i=1; i<=n; i++) {
if ((school[i]&&home[i]==0)||!school[i]) {
memset(vis,0,sizeof(vis));
if (match(i)) ++sum;
}
}
if (sum==tot)
cout<<"^_^"< P1365 WJMZBMR打osu! / Easy
期望dp入门。
给出o,x，?串，将其中所有的?等概率替换为o,x，求所有连续o串长度的平方和。
设以i-1结尾的连续段长度期望为len，递推以i结尾的连续段长度：
若第i次为o,则len++，若为x则直接置为0。若为?:
设到i-1得到的分数为score，若为 o , 则 \(\Delta score=(len+1)^2-len^2=2len+1\),若为 x 则不变。若为 ? :
不要被卡精度。。。
#include
#include
using namespace std;
int n;
double len=0,score=0;
string s;
int main() {
cin>>n>>s;
s=' '+s;
for (int i=1; i<=n; i++) {
if (s[i]=='x') {
score=score;
len=0;
}
if (s[i]=='o') {
score+=len*2+1;
len++;
}
if (s[i]=='?'){
score=((score+(score+len*2+1))*1.0)/(2*1.0);
len=((0+(len+1))*1.0/2*1.0);
}
}
printf("%.4lf",score);
}
一点想法，似乎不对。
第一次：
\[P_1(i)=p_i\prod_{j第二次：
\[P_2(i)=\sum_k^{i-1} \frac{P_1(k)}{(1-p_k)}p_i\prod_{jP7687 [CEOI2005] Critical Network Lines
给出一张无向图，其中一些点有性质A/B，问哪些边断开之后形成的连通块中有连通块没有任何特殊性质结点。
首先该边必然是割边，但求取特殊性质节点个数比较困难。
这里使用一个特殊技巧：在tarjan形成的搜索树上dp。
#include
#include
using namespace std;
const int N=1000005,M=2000005;
int n,m,K,L,cnt,tot,ans;
int head[N],a[N],b[N],dfn[N],low[N],resf[N],rest[N];
struct edge {
int from,to,next;
} e[M];
void add(int u,int v) {
e[++cnt].to=v;
e[cnt].from=u;
e[cnt].next=head[u];
head[u]=cnt;
}
void tarjan(int k,int bef) {
dfn[k]=low[k]=++tot;
for (int i=head[k]; i; i=e[i].next) {
int v=e[i].to;
if (!dfn[v]) {
tarjan(v,k);
low[k]=min(low[k],low[v]);
if (low[v]>dfn[k]) {
if (!a[v]||!b[v]||a[v]==K||b[v]==L) {
ans++;
resf[ans]=k,rest[ans]=v;
}
}
a[k]+=a[v],b[k]+=b[v];
}
if (v!=bef) low[k]=min(low[k],dfn[v]);
}
}
int x,y;
int main() {
ios::sync_with_stdio(false);
cin>>n>>m>>K>>L;
for (int i=1; i<=K; i++) {
int x;
cin>>x;
a[x]=1;
}
for (int i=1; i<=L; i++) {
int x;
cin>>x;
b[x]=1;
}
for (int i=1; i<=m; i++) {
cin>>x>>y;
add(x,y);
add(y,x);
}
tarjan(1,0);
cout< T211568 Perm
给定一个排列，每次操作可以把相邻两个数变成较小值。问任意操作任意次后能形成多少种序列。
单调栈/扫描线，感觉难度较大。
#include
#include
#define int long long
using namespace std;
const int N = 2000005, MOD = 1000000007;
int n, top;
int a[N], stack[N], sum1[N], sum2[N];
signed main()
{
// freopen("perm.in", "r", stdin);
// freopen("perm.out", "w", stdout);
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
while (top && a[stack[top]] > a[i])
top--;
int temp = (sum1[i - 1]%MOD - sum1[stack[top]]%MOD + (top == 0ll ? 1ll : sum2[top]%MOD)+MOD)%MOD;
stack[++top] = i;
sum1[i] = (sum1[i - 1]%MOD + temp%MOD)%MOD;
sum2[top] = (sum2[top - 1]%MOD + temp%MOD)%MOD;
}
cout << sum2[top]%MOD << endl;
}
P6268 [SHOI2002]舞会
二分图最大独立集模板。
运用公式：二分图最小点覆盖=二分图最大匹配=n-二分图最大独立集。
注意题目中没有给定二分图的左右点划分，使用染色或者直接计算然后除2。
#include
#include
#include
using namespace std;
const int N=2005;
int n,m;
int p[N],vis[N];
int mp[N][N];
bool ntr(int k) {
for (int i=1; i<=n; i++) {
if (!mp[k][i]||vis[i]) continue;
vis[i]=1;
if (!p[i]||ntr(p[i])) {
p[i]=k;
return true;
}
}
return false;
}
int match() {
int tot=0;
for (int i=1; i<=n; i++) {
for (int j=1;j<=n;j++)
vis[j]=0;
if (ntr(i)) tot++;
}
return tot;
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++) {
int u,v;
cin>>u>>v;
u++,v++;
mp[u][v]=1;
mp[v][u]=1;
}
cout< P1197 [JSOI2008]星球大战
没能一遍A图论绿题，感觉要凉。
每次操作删点，询问连通块个数。
显然离线倒序转化为加边，使用并查集维护。
注意细节：删的点不属于连通块。
#include
#include
using namespace std;
const int N=500005;
int n,m,k,cnt;
int u[N],v[N],des[N],fa[N],num[N],ans[N];
int find(int k) {
return fa[k]==k?k:fa[k]=find(fa[k]);
}
void unionn(int a,int b) {
int f1=find(a),f2=find(b);
if (f1==f2) return;
fa[f1]=f2;
cnt--;
}
struct edge {
int to,next;
} e[N];
int tot,head[N];
void add(int u,int v) {
e[++tot].to=v;
e[tot].next=head[u];
head[u]=tot;
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
for (int i=0; i<=n; i++)
fa[i]=i;
for (int i=1; i<=m; i++) {
cin>>u[i]>>v[i];
add(u[i],v[i]);
add(v[i],u[i]);
}
cin>>k;
for (int i=1; i<=k; i++) {
cin>>des[i];
num[des[i]]=1;
}
cnt=n-k;
for (int i=1; i<=m; i++)
if (!num[u[i]]&&!num[v[i]])
unionn(u[i],v[i]);
ans[k+1]=cnt;
for (int i=k; i>=1; i--) {
cnt++;
num[des[i]]=0;
for (int j=head[des[i]]; j; j=e[j].next) {
if (!num[e[j].to])
unionn(des[i],e[j].to);
}
ans[i]=cnt;
}
for (int i=1; i<=k+1; i++)
cout< P3385 [模板] 负环/[模板] Shortest Path Dead Algorithm
DEAD是一种简单的最短路算法，可以处理负权边。
如果入队次数大于n即为存在负环。注意队列弹出后要清除该点vis数组。
#include
#include
#include
using namespace std;
const int N=1000005,M=1000005;
const long long INF=0x7ffffffffff;
int T,n,m;
int vis[N],rin[N];
long long dis[N];
queue q;
struct edge {
int to,next;
long long d;
} e[M];
int cnt,head[N];
void add(int u,int v,long long d) {
e[++cnt].to=v;
e[cnt].next=head[u];
e[cnt].d=d;
head[u]=cnt;
}
bool dead() {
for (int i=1; i<=n; i++) dis[i]=INF;
while (!q.empty()) q.pop();
q.push(1),rin[1]++,dis[1]=0,vis[1]=1;
while (!q.empty()) {
int x=q.front();
q.pop(),vis[x]=0;
for (int i=head[x]; i; i=e[i].next) {
int v=e[i].to;
if (dis[v]>dis[x]+e[i].d) {
dis[v]=dis[x]+e[i].d;
if (!vis[v]) {
vis[v]=1;
q.push(v);
rin[v]++;
if (rin[v]>n) return true;
}
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin>>T;
while (T--) {
cin>>n>>m;
for (int i=1; i<=n; i++) head[i]=0,rin[i]=0,vis[i]=0;
cnt=0;
for (int i=1; i<=m; i++) {
int u=0,v=0;
long long d=0;
cin>>u>>v>>d;
add(u,v,d);
if (d>=0) add(v,u,d);
}
if (dead()) cout<<"YES"<