2022.10 OI学习笔记（下）
前言：
这是 2022.10 OI学习笔记（下）……
转眼间，7年的OI生涯已经接近尾声了。
回望过去，OI在我迄今为止的人生选择中，发挥了重要的作用。可以说，没有OI，不仅不会有现在在机房中作为一个OIer的“我”，也不会有那个在whk教室中的作为一个物化技选手的“我”。
那么，希望在接下来的一个多月里，至少在过程中，为整个OI生涯画上一个圆满的句号。
————————————————————
2022.10.17
红名了，好诶！
————————————
1.CF1738C Even Number Addicts
前些天打CF的一道C题，当时赛场上没有写出来（然后掉分了qwq）
参考的一份题解
#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>n;
int sum1=0,sum2=0;
for (int i=1;i<=n;i++) {
int x; cin>>x;
if (x&1) sum2++;
else sum1++;
}
if (sum2%4==0) cout<<"Alice\n";
else if (sum2%4==1) {
if (sum1%2==1) cout<<"Alice\n";
else cout<<"Bob\n";
}
else if (sum2%4==2) {
cout<<"Bob\n";
}
else cout<<"Alice\n";
}
return 0;
}————————————
2.P1080 [NOIP2012 提高组] 国王游戏
参考的一份题解（关注贪心证明）
要点：
-
贪心！（可以看一下题解，其实很多题的贪心都是这个套路来推式子）
-
高精除以低精（以前没有写过qwq）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
struct qwq{int a,b;}x[N];
struct QAQ{int a[150005],num;}cc,bb,pro,tmp,ans;
int n,A;
void wr(QAQ aa) {
for (int i=aa.num;i>=1;i--)
cout<<aa.a[i];
}
bool cmp(qwq X,qwq Y) {
return X.a*X.b<Y.a*Y.b;
}
void cl(QAQ &c) {
for (int i=1;i<=c.num;i++) c.a[i]=0;
c.num=0;
}
QAQ times(QAQ aa,int B) {
cl(cc);
int tot=0;
while (B) {
bb.a[++tot]=B%10;
B/=10;
}
bb.num=tot;
for (int i=1;i<=aa.num;i++)
for (int j=1;j<=bb.num;j++)
cc.a[i+j-1]+=aa.a[i]*bb.a[j];
cc.num=aa.num+bb.num;
for (int i=1;i<=cc.num;i++) {
if (cc.a[i]>=10) {
cc.a[i+1]+=cc.a[i]/10;
cc.a[i]%=10;
}
}
while (cc.a[cc.num]==0&&cc.num>=2) cc.num--;
return cc;
}
QAQ div(QAQ aa,int B){
int x=0;
cl(cc);
for (int i=aa.num;i>=1;i--) {
x=x*10+aa.a[i];
cc.a[i]=x/B;
x%=B;
}
cc.num=aa.num;
while (cc.a[cc.num]==0&&cc.num>=2) cc.num--;
return cc;
}
void copy(QAQ &aa,QAQ &bb) {
for (int i=1;i<=bb.num;i++) {
aa.a[i]=bb.a[i];
}
aa.num=bb.num;
}
bool more(QAQ aa,QAQ bb) {
if (aa.num>bb.num) return 1;
for (int i=aa.num;i>=1;i--) {
if (aa.a[i]>bb.a[i]) return 1;
if (aa.a[i]<bb.a[i]) return 0;
}
return 0;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=0;i<=n;i++) {
cin>>x[i].a>>x[i].b;
}
sort(x+1,x+n+1,cmp);
pro.a[1]=1;pro.num=1;
for (int i=0;i<=n;i++) {
tmp=div(pro,x[i].b);
if (more(tmp,ans)) copy(ans,tmp);
pro=times(pro,x[i].a);
}
wr(ans);
return 0;
}————————————
3.P1137 旅行计划
一道拓扑+DP……
不述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,m,tot,head[N];
int ru[N],chu[N],dp[N];
struct qwq{
int to,hext;
}e[N];
queue <int> q;
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=1;i<=m;i++) {
int x,y;
cin>>x>>y;
add(x,y);
ru[y]++,chu[x]++;
}
for (int i=1;i<=n;i++) dp[i]=1;
for (int i=1;i<=n;i++) {
if (ru[i]==0) {
dp[i]=1;
q.push(i);
}
}
while (!q.empty()) {
int u=q.front(); q.pop();
for (int i=head[u];i;i=e[i].hext) {
int v=e[i].to;
ru[v]--;
dp[v]=max(dp[u]+1,dp[v]);
if (ru[v]==0) {
q.push(v);
}
}
}
for (int i=1;i<=n;i++) cout<<dp[i]<<'\n';
return 0;
}————————————
4.CF2B The least round way
/*
f1[i][j]:表示从(1,1)到(i,j)所需要的最少的5的个数
f2[i][j]:表示从(1,1)到(i,j)所需要的最少的2的个数
*/要点：
-
第一处
//!!!处，一开始误打成f1了emmmm -
第二处
//!!!处，别忘记考虑路径中有0的情况！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1003;
const int inf=1e9+7;
int n,a[N][N],f1[N][N],f2[N][N],kx,ky;
char pre1[N][N],pre2[N][N];
string ans;
int num2(int x) {
if (x==0) return 1;
int t=0;
while (x%2==0) {
x/=2;
t++;
}
return t;
}
int num5(int x) {
if (x==0) return 1;
int t=0;
while (x%5==0) {
x/=5;
t++;
}
return t;
}
void dfs1(int x,int y) {
if (x<=0||y<=0) return ;
if (x==1&&y==1) return ;
if (pre1[x][y]=='D') {
dfs1(x-1,y);
}
else dfs1(x,y-1);
ans+=pre1[x][y];
}
void dfs2(int x,int y) {
if (x<=0||y<=0) return ;
if (x==1&&y==1) return ;
if (pre2[x][y]=='D') {
dfs2(x-1,y);
}
else dfs2(x,y-1);
ans+=pre2[x][y];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
bool tf=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) {
cin>>a[i][j];
if (a[i][j]==0) {
tf=1;
kx=i,ky=j;
}
}
for (int i=1;i<=n;i++)
f1[i][0]=f1[0][i]=f2[i][0]=f2[0][i]=inf;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) {
if (i==1&&j==1) {
f1[i][j]=num5(a[i][j]);
continue;
}
if (f1[i-1][j]<f1[i][j-1]) {
f1[i][j]=f1[i-1][j]+num5(a[i][j]);
if (!((i==1)&&(j==1))) pre1[i][j]='D';
}
else {
f1[i][j]=f1[i][j-1]+num5(a[i][j]);
if (!((i==1)&&(j==1))) pre1[i][j]='R';
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) {
if (i==1&&j==1) {
f2[i][j]=num2(a[i][j]); //!!!
continue;
}
if (f2[i-1][j]<f2[i][j-1]) {
f2[i][j]=f2[i-1][j]+num2(a[i][j]);
if (!((i==1)&&(j==1))) pre2[i][j]='D';
}
else {
f2[i][j]=f2[i][j-1]+num2(a[i][j]);
if (!((i==1)&&(j==1))) pre2[i][j]='R';
}
}
if (tf==1) { //!!!
if (!(f1[n][n]==0||f2[n][n]==0)) {
cout<<1<<'\n';
for (int i=1;i<=kx-1;i++) cout<<'D';
for (int i=1;i<=ky-1;i++) cout<<'R';
for (int i=kx+1;i<=n;i++) cout<<'D';
for (int i=ky+1;i<=n;i++) cout<<'R';
return 0;
}
}
if (f1[n][n]<=f2[n][n]) {
cout<<f1[n][n]<<'\n';
dfs1(n,n);
cout<<ans<<'\n';
}
else {
cout<<f2[n][n]<<'\n';
dfs2(n,n);
cout<<ans<<'\n';
}
return 0;
}————————————
5.CF543A Writing Code
参考的一份题解
其实是一道很简单的背包，但是自己在抽象与建模这步想得不是很清楚……
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,m,B,MOD,a[N],dp[505][505];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>B>>MOD;
for (int i=1;i<=n;i++) cin>>a[i];
dp[0][0]=1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
for (int t=a[i];t<=B;t++)
dp[j][t]=(dp[j][t]+dp[j-1][t-a[i]])%MOD;
}
}
int ans=0;
for (int i=0;i<=B;i++) {
ans=(ans+dp[m][i])%MOD;
}
cout<<ans;
return 0;
}————————————
6.P1279 字串距离
dp[i][j]：匹配到a子串的i位和b子串的j位，总距离的最小值。要点：
-
//!!!处，这个也要记得判！ -
如 hack 数据：
rcpw wbl 1答案为： rcpw___ ___wbl_
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2003;
char a[N],b[N];
int k,dp[N][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>a>>b;
cin>>k;
int na=strlen(a),nb=strlen(b);
for (int i=na;i>=1;i--) a[i]=a[i-1];
for (int i=nb;i>=1;i--) b[i]=b[i-1];
if (na<nb) {
for (int i=na+1;i<=nb;i++) a[i]='0';
}
else {
for (int i=nb+1;i<=na;i++) b[i]='0';
}
for (int i=1;i<=max(na,nb);i++) dp[0][i]=dp[i][0]=k*i;
for (int i=1;i<=max(na,nb);i++)
for (int j=1;j<=max(na,nb);j++) {
if (a[i]=='0'||b[j]=='0') {
dp[i][j]=dp[i-1][j-1]+k;
if (a[i]=='0') dp[i][j]=min(dp[i][j],dp[i-1][j]); //!!!
else dp[i][j]=min(dp[i][j],dp[i][j-1]);
}
else dp[i][j]=dp[i-1][j-1]+abs(a[i]-b[j]);
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1])+k,dp[i][j]);
}
cout<<dp[max(na,nb)][max(na,nb)];
return 0;
}————————————
7.AT4526 Knapsack 2
一道数据范围不太一样的01背包。
不过一开始一直没有想出来解法emmmm……
看了题解才知道咳咳……
//dp[i]:总价值为i所需的最小容量 #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2003;
const int inf=1e9+7;
int n,V,v[N],w[N];
int dp[N*N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>V;
for (int i=1;i<=n;i++) {
cin>>v[i]>>w[i];
}
int B=n*1000;
for (int i=1;i<=B;i++) dp[i]=inf;
dp[0]=0;
for (int i=1;i<=n;i++) {
for (int j=B;j>=w[i];j--)
dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
}
for (int i=B;i>=0;i--) {
if (dp[i]<=V) {
cout<<i;
break;
}
}
return 0;
}————————————
8.AT4530 Coins
不述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3003;
int n;
double p[N],dp[N][N];
signed main(){
scanf("%lld",&n);
dp[0][0]=1;
for (int i=1;i<=n;i++) scanf("%lf",&p[i]);
for (int i=1;i<=n;i++) {
dp[i][0]=dp[i-1][0]*(1-p[i]);
for (int j=1;j<=i-1;j++) {
dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
}
dp[i][i]=dp[i-1][i-1]*p[i];
}
double ans=0.0;
for (int i=0;i<=n;i++)
if (i>n-i) ans+=dp[n][i];
printf("%.12lf\n",ans);
return 0;
}————————————
9.AT4531 Sushi
参考的一份题解
感觉是今天做的比较有难度的一道题了，不过又还没难到以自己的能力完全没法理解。
要点：
- 注意循环顺序！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=333;
int n,sum1,sum2,sum3,a[N];
double dp[N][N][N];
signed main() {
scanf("%lld",&n);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
for (int i=1;i<=n;i++) {
if (a[i]==1) sum1++;
if (a[i]==2) sum2++;
if (a[i]==3) sum3++;
}
for (int k=0;k<=n;k++)
for (int j=0;j<=n;j++)
for (int i=0;i<=n;i++) {
if (i==0&&j==0&&k==0) continue;
dp[i][j][k]=n;
if (i) dp[i][j][k]+=i*dp[i-1][j][k];
if (j) dp[i][j][k]+=j*dp[i+1][j-1][k];
if (k) dp[i][j][k]+=k*dp[i][j+1][k-1];
dp[i][j][k]/=((i+j+k)*1.0);
}
printf("%.12lf\n",dp[sum1][sum2][sum3]);
return 0;
}————————————
10.AT4534 Candies
要点：
- 对于
b数组也要记得取模！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
const int MOD=1e9+7;
int n,k,a[N],dp[3][N],b[3][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for (int i=1;i<=n;i++) cin>>a[i];
dp[0][0]=1;
b[0][0]=1; for (int j=1;j<=k;j++) b[0][j]=b[0][j-1]+dp[0][j];
for (int i=1;i<=n;i++) {
for (int j=0;j<=k;j++) {
if (j>a[i]) dp[i&1][j]=((b[(i+1)&1][j])%MOD-b[(i+1)&1][j-a[i]-1]+MOD)%MOD;
if (j==a[i]) dp[i&1][j]=b[(i+1)&1][j]%MOD;
if (j<a[i]) dp[i&1][j]=b[(i+1)&1][j]%MOD;
}
b[i&1][0]=dp[i&1][0];
for (int j=1;j<=k;j++) b[i&1][j]=(b[i&1][j-1]+dp[i&1][j])%MOD; //%MOD!!!
}
cout<<(dp[n&1][k]%MOD);
return 0;
}————————————
11.AT4537 Independent Set
一道简单的树形DP……
不述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
const int MOD=1e9+7;
struct qwq{
int hext,to;
}e[N];
int n,tot,head[N],dp[N][3];
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int x,int fath) {
dp[x][0]=dp[x][1]=1;
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,x);
dp[x][0]=dp[x][0]*(dp[v][0]+dp[v][1])%MOD;
dp[x][1]=dp[x][1]*dp[v][0]%MOD;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n-1;i++) {
int x,y; cin>>x>>y;
add(x,y); add(y,x);
}
dfs(1,0);
int ans=(dp[1][0]+dp[1][1])%MOD;
cout<<ans;
return 0;
}————————————————————
2022.10.18
1.AT4538 Flowers
一道DP+树状数组。
和前几天的一道题挺类似的……
要点：
- 最大值可以用树状数组维护！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,dp[N],tree[N];
struct qwq{int h,a;}x[N];
int lowbit(int x) { return x&(-x); }
void add(int x,int k) {
for (;x<=n;x+=lowbit(x)) tree[x]=max(tree[x],k);
}
int query(int x) {
int tmp=0;
for (;x>0;x-=lowbit(x)) tmp=max(tmp,tree[x]);
return tmp;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) cin>>x[i].h;
for (int i=1;i<=n;i++) cin>>x[i].a;
for (int i=1;i<=n;i++) {
dp[i]=query(x[i].h-1)+x[i].a;
/*
for(int j=0;j<=i;j++)
if (x[j].h<x[i].h) dp[i]=max(dp[i],dp[j]+x[i].a);
*/
add(x[i].h,dp[i]);
}
int ans=0;
for (int i=1;i<=n;i++) ans=max(ans,dp[i]);
cout<<ans;
return 0;
} ————————————
2.AT4539 Walk
一道矩阵快速幂+DP……
代码实现上并不难，但是思路自己还是比较生疏的。
复习时可以再跟着题解走一遍。
参考的一份题解
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct qwq{
int siz;
int v[1003][1003];
}now,a,tmp,z;
const int MOD=1e9+7;
int n,k,ans;
void cl(qwq &z) {
for (int i=1;i<=z.siz;i++)
for (int j=1;j<=z.siz;j++)
z.v[i][j]=0;
}
qwq operator * (const qwq &x,const qwq &y) {
cl(z); z.siz=x.siz;
for (int k=1;k<=x.siz;k++)
for (int i=1;i<=x.siz;i++)
for (int j=1;j<=x.siz;j++)
z.v[i][j]=(z.v[i][j]+x.v[i][k]*y.v[k][j]%MOD)%MOD;
return z;
}
qwq mi(qwq A,int B) {
tmp.siz=A.siz;
for (int i=1;i<=A.siz;i++)
for (int j=1;j<=A.siz;j++)
tmp.v[i][j]=0;
for (int i=1;i<=A.siz;i++) tmp.v[i][i]=1;
while (B) {
if (B&1) tmp=tmp*A;
A=A*A;
B>>=1;
}
return tmp;
}
signed main(){
cin>>n>>k;
a.siz=n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) {
cin>>a.v[i][j];
}
now=mi(a,k);
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
ans+=now.v[i][j];
ans%=MOD;
}
}
cout<<ans;
return 0;
}————————————
3.CF1325C Ehab and Path-etic MEXs
一道挺巧妙的构造。
参考的一份题解
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=300005;
struct qwq{int hext,to,w;}e[N];
int head[N],ans[N],son[N],n,k,cnt,tot;
void add(int x,int y,int z) {
e[++tot].to=y;
e[tot].hext=head[x];
e[tot].w=z;
head[x]=tot;
}
void dfs(int x,int fath) {
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,x);
son[x]++;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n-1;i++) {
int x,y;
cin>>x>>y;
add(x,y,i);add(y,x,i);
}
dfs(1,0);
for (int i=1;i<=n;i++) {
if ((int)(i!=1)+son[i]>=3) {
k=i;
break;
}
}
for (int i=head[k];i;i=e[i].hext) {
ans[e[i].w]=++cnt;
}
for (int i=1;i<=n-1;i++)
if (!ans[i]) ans[i]=++cnt;
for (int i=1;i<=n-1;i++)
cout<<ans[i]-1<<'\n';
return 0;
}————————————
4.CF1383A String Transformation 1
参考的一份题解
自己确实看不出来是一道并查集（悲）……
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int T,n,fa[N];
string sta,stb;
int find(int x) {
if (fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>n;
cin>>sta>>stb;
bool tf=1;
for (int i=0;i<n;i++)
if (sta[i]>stb[i]) {
tf=0;
cout<<-1<<endl;
break;
}
if (tf) {
int ans=0;
for (int i=1;i<=20;i++) fa[i]=i;
for (int i=0;i<n;i++) {
int fx=find(sta[i]-'a'+1),fy=find(stb[i]-'a'+1);
if (fx==fy) continue;
fa[fx]=fy;
ans++;
}
cout<<ans<<endl;
}
}
return 0;
}————————————
5.CF1360E Polygon
今天为数不多的自己写出来的题（惭愧）……
要点：
- 记得记忆化！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=55;
int a[N][N],vis[N][N];
int T,n;
string st;
void dfs(int x,int y) {
if (vis[x][y]) return ;
vis[x][y]=1;
if (a[x-1][y]) dfs(x-1,y);
if (a[x][y-1]) dfs(x,y-1);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>n;
for (int i=1;i<=n;i++) {
cin>>st;
for (int j=0;j<n;j++)
a[i][j+1]=st[j]-'0';
}
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++) {
if (a[i][n]) dfs(i,n);
if (a[n][i]&&i!=n) dfs(n,i);
}
bool tf=1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
if (a[i][j] && !vis[i][j]) tf=0;
}
}
if (tf) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}————————————
6.CF1365D Solve The Maze
参考的一份题解
要点：
- 贪心：封闭每一个
B（证明可以见题解）。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const int N=55;
int T,n,m,a[N][N],tag[N][N],vis[N][N];
string st;
void dfs(int x,int y) {
if (vis[x][y]) return ;
vis[x][y]=1;
if (a[x][y]>1) tag[x][y]=1;
if (a[x][y]==0) return ;
for (int i=0;i<4;i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if (nx<1||nx>n||ny<1||ny>m) continue;
if (a[nx][ny]==0) continue;
dfs(nx,ny);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>n>>m;
for (int i=1;i<=n;i++) {
cin>>st;
for (int j=0;j<m;j++) {
if (st[j]=='.') a[i][j+1]=1;
if (st[j]=='#') a[i][j+1]=0;
if (st[j]=='G') a[i][j+1]=2;
if (st[j]=='B') a[i][j+1]=3;
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i][j]==3) {
for (int k=0;k<4;k++) {
int nx=i+dx[k],ny=j+dy[k];
if (a[nx][ny]==1) a[nx][ny]=0;
}
}
memset(tag,0,sizeof(tag));
memset(vis,0,sizeof(vis));
dfs(n,m);
bool tf=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
if (a[i][j]==2&&tag[i][j]==0) tf=0;
if (a[i][j]==3&&tag[i][j]==1) tf=0;
}
if (tf) cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
return 0;
}————————————
7.CF1324F Maximum White Subtree
一道树形DP……
参考的一份题解
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=400005;
struct qwq{int hext,to;}e[N];
int n,tot,head[N],a[N];
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int x,int fath) {
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,x);
if (a[v]>0) a[x]+=a[v];
}
}
void DFS(int x,int fath) {
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
if (a[v]>0) a[v]=max(a[v],a[x]);
else a[v]=max(a[v],a[x]+a[v]);
DFS(v,x);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) {
if (a[i]==0) a[i]=-1;
}
for (int i=1;i<=n-1;i++) {
int x,y; cin>>x>>y;
add(x,y); add(y,x);
}
dfs(1,0);
DFS(1,0);
for (int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}————————————
8.CF1369D TediousLee
一道递推。
其实已经在草稿纸上把图画出来了的，但是没有往这个方面去想，一直想着去写通项然后失败了emmmm……
参考的一份题解
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2000006;
const int MOD=1e9+7;
int T,n,f[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
f[1]=0,f[2]=0;
for (int i=3;i<=2e6;i++)
if (i%3==0) f[i]=f[i-1]+2*f[i-2]+4,f[i]%=MOD;
else f[i]=f[i-1]+2*f[i-2],f[i]%=MOD;
while (T--) {
cin>>n;
cout<<f[n]<<endl;
}
return 0;
}————————————
9.P5911 [POI2004]PRZ
一道枚举子集类的状态压缩。
参考的一份题解
重点关注 //!!! 处枚举子集的相关部分！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=(1<<16)+5;
const int inf=1e9+7;
int V,n,dp[N],t[233],T[N],w[233],W[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>V>>n;
for (int i=1;i<=n;i++) {
cin>>t[i]>>w[i];
}
for (int i=0;i<(1<<n);i++) {
for (int j=1;j<=n;j++) {
if (i&(1<<(j-1))) {
T[i]=max(T[i],t[j]);
W[i]+=w[j];
}
}
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for (int i=0;i<(1<<n);i++) {
for (int j=i;;j=i&(j-1)) { //!!!
if (W[i^j]<=V) dp[i]=min(dp[i],dp[j]+T[i^j]);
if (j==0) break;
}
}
cout<<dp[(1<<n)-1];
return 0;
}————————————
10.CF1336A Linova and Kingdom
参考的一份题解
很妙的一道题。
思路自己是有的，但是没有能够将其量化表示出来（）……
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=400005;
struct qwq{int hext,to;}e[N];
struct QAQ{int siz,dep;}a[N];
int n,tot,k,head[N];
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int x,int fath) {
a[x].dep=a[fath].dep+1;
a[x].siz=1;
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,x);
a[x].siz+=a[v].siz;
}
}
bool cmp(QAQ x,QAQ y) {
return x.dep-x.siz>y.dep-y.siz;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for (int i=1;i<=n-1;i++) {
int x,y; cin>>x>>y;
add(x,y); add(y,x);
}
dfs(1,0);
sort(a+1,a+n+1,cmp);
int ans=0;
for (int i=1;i<=k;i++)
ans+=(a[i].dep-1)-(a[i].siz-1);
cout<<ans;
return 0;
}————————————————————
2022.10.19
通过1k了，好耶！
1.UVA532 Dungeon Master
昨天晚上写的一道题，一直到今天早上再交才总算爬到了结果qwq……
代码没什么好说的，不述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int dx[]={1,-1,0,0,0,0};
const int dy[]={0,0,1,-1,0,0};
const int dz[]={0,0,0,0,1,-1};
struct qwq{int x,y,z;};
const int N=33;
bool tf;
string st;
int n,m,h,ans,a[N][N][N];
int sx,sy,sz,tx,ty,tz,vis[N][N][N];
queue <qwq> q;
void bfs() {
while (!q.empty()) q.pop();
q.push((qwq){sx,sy,sz});
vis[sx][sy][sz]=0;
while (!q.empty()) {
int x=q.front().x,y=q.front().y,z=q.front().z;
q.pop();
if (x==tx&&y==ty&&z==tz) {
tf=1;
ans=vis[x][y][z];
return ;
}
for (int i=0;i<6;i++) {
int nx=x+dx[i],ny=y+dy[i],nz=z+dz[i];
if (nx<1||nx>n||ny<1||ny>m||nz<1||nz>h) continue;
if (a[nx][ny][nz]) continue;
if (vis[nx][ny][nz]!=-1) continue;
vis[nx][ny][nz]=vis[x][y][z]+1;
q.push((qwq){nx,ny,nz});
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>h>>n>>m;
while (h&&n&&m) {
tf=0;
memset(vis,-1,sizeof(vis));
memset(a,0,sizeof(a));
for (int k=1;k<=h;k++) {
for (int i=1;i<=n;i++) {
cin>>st;
for (int j=0;j<m;j++) {
if (st[j]=='S') sx=i,sy=j+1,sz=k;
if (st[j]=='E') tx=i,ty=j+1,tz=k;
if (st[j]=='#') a[i][j+1][k]=1;
}
}
}
bfs();
if (tf) {
cout<<"Escaped in "<<ans<<" minute(s)."<<endl;
}
else cout<<"Trapped!"<<endl;
cin>>h>>n>>m;
}
return 0;
}————————————
2.P7666 [JOI2018] Stove
今天模拟赛的T1……
不述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,k,cnt,t[N],a[N];
bool cmp(int x,int y) {
return x<y;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for (int i=1;i<=n;i++) cin>>t[i];
for (int i=1;i<=n-1;i++) a[++cnt]=t[i+1]-t[i]-1;
sort(a+1,a+cnt+1,cmp);
int ans=0;
for (int i=1;i<=n-k;i++)
ans+=a[i];
ans+=n;
cout<<ans<<endl;
return 0;
} ————————————
3.AT_dp_t Permutation
参考的一份题解
要点：
- 转移
F(i,j)时，我们可以将前i-1个数中>=j的数全部加1以保证填入的是排列 —— 这一步自己确实没有想到
其它的话就是前缀和优化DP了，这个是很基础的套路了，自己应该没有什么问题qwq……
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3003;
const int MOD=1e9+7;
int n,b[N][N],dp[N][N];
string st;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
cin>>st;
dp[1][1]=1;
for (int i=1;i<=n;i++) b[1][i]=(b[1][i-1]+dp[1][i])%MOD;
for (int i=2;i<=n;i++) {
for (int j=1;j<=i;j++) {
if (st[i-2]=='<') dp[i][j]=b[i-1][j-1]%MOD;
else dp[i][j]=(b[i-1][i-1]-b[i-1][j-1]+MOD)%MOD;
}
for (int j=1;j<=i;j++) b[i][j]=(b[i][j-1]+dp[i][j])%MOD;
}
int ans=b[n][n];
cout<<ans;
return 0;
}————————————
4.P8365 [LNOI2022] 吃
模拟赛的T2……
模拟赛时的乱搞做法侥幸得了85分的高分（20/20的dfs+20/20的爬山+45/60的乱搞贪心）……
赛时过的人并不多，不过赛后回看，这还是一道能订正的题qwq
参考的一份题解
思路：
-
易得，
a[i]==1时我们肯定选择去加b[i]（这个赛时自己也想到了qwq） -
我们可以证得，
a[i]>=2的部分，我们最多选择一个去加b[i]，其它都是乘（其实这个也不难，感性理解一下就行） -
再推一下，我们就可以通过比较知道我们到底要将剩下的哪个用来加（式子看一下题解就行了）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
const int MOD=1e9+7;
int n,ans,p,a[N],b[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) cin>>b[i];
ans=1;
for (int i=1;i<=n;i++) {
if (a[i]==1) ans=(ans+b[i])%MOD;
}
double maxn=ans;
for (int i=1;i<=n;i++) {
if (a[i]==1) continue;
if ((ans+b[i])/(a[i]*1.0)>maxn) {
maxn=(ans+b[i])/(a[i]*1.0);
p=i;
}
}
ans=(ans+b[p])%MOD;
for (int i=1;i<=n;i++) {
if (i!=p) ans=(ans*a[i])%MOD;
}
cout<<ans;
return 0;
}————————————
5.CF582A GCD Table
自己思路大概是有的，但细节处理不到位（悲）。
一篇题解（MK写的）
不过复习时看一下自己blog就够了，这篇题解只是帮助debug用的（笑）。
要点：
- 关注自己代码中的注释！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=250005;
int n,a[N],ans[N],cnt;
map <int,int> vis;
map <int,int> p;
bool cmp(int x,int y) {
return x>y;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n*n;i++) cin>>a[i];
for (int i=1;i<=n*n;i++) p[a[i]]++;
sort(a+1,a+n*n+1,cmp);
for (int i=1;i<=n*n&&cnt<n;i++) {
if (vis[a[i]]<p[a[i]]) { //这个数还没用光才需要执行
for (int j=1;j<=p[a[i]]-vis[a[i]]&&cnt<n;j++) {
ans[++cnt]=a[i];
cout<<a[i]<<" ";
vis[a[i]]++; //gcd(a[i],a[i])=1
for (int k=1;k<cnt;k++) { //要放在j循环的里面，每多一个ans[cnt]就要执行
vis[__gcd(a[i],ans[k])]+=2;
}
}
}
if (a[i]==1) {
for (int j=1;j<=n-cnt;j++) cout<<1<<" ";
break;
}
}
return 0;
}————————————
6.CF687B Remainders Game
结论应该模拟一下就能出来。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000006;
int a[N],b[N],cnt,n,k;
bool vis[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for (int i=2;i<=(int)sqrt(k);i++) {
if (k%i==0) {
k/=i; //别忘了!!!
b[++cnt]=i;
while (k%i==0) {
k/=i;
b[cnt]*=i;
}
}
}
if (k>1) b[++cnt]=k;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) {
for (int j=1;j<=cnt;j++)
if (a[i]%b[j]==0) vis[j]=1;
}
bool tf=1;
for (int i=1;i<=cnt;i++) if (!vis[i]) tf=0;
if (tf) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}————————————
7.CF573E Bear and Bowling
一道黑题（至少目前是）……
不过用 O(n^2) 的DP+C++20 水过去了……
参考的一份题解
dp[x]表示现在子序列有x个元素的答案最大值。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int n,ans,a[N],dp[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) dp[i]=-1e18;
ans=0;
for (int i=1;i<=n;i++) {
for (int j=i;j>=1;j--) {
dp[j]=max(dp[j],dp[j-1]+j*a[i]);
}
}
for (int i=1;i<=n;i++) {
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}————————————
8.CF1328E Tree Queries
一道独立做出的蓝题……
思路：
-
将题意转化一下，即：每个点的父节点是否都在一条以
根节点1为一端的链上。 -
然后通过倍增判断即可。
要点：
-
fa数组的第二维要开足！ -
无向边数组要开两倍！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,Q,tot;
int fa[N][21],lg[N],dep[N],head[N];
struct QAQ{int to,hext;}e[N<<1];
struct qwq{int x,d;}a[N];
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int x,int fath) {
dep[x]=dep[fath]+1;
fa[x][0]=fath;
for (int j=1;j<=19;j++) {
fa[x][j]=fa[fa[x][j-1]][j-1];
}
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,x);
}
}
bool cmp(qwq X,qwq Y) {
return X.d>Y.d;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>Q;
for (int i=1;i<=n-1;i++) {
int x,y; cin>>x>>y;
add(x,y); add(y,x);
}
for (int i=1;i<=n;i++) lg[i]=(int)log2(i)+1;
dfs(1,1);
while (Q--) {
int k; cin>>k;
for (int i=1;i<=k;i++) cin>>a[i].x;
for (int i=1;i<=k;i++) a[i].x=fa[a[i].x][0];
for (int i=1;i<=k;i++) a[i].d=dep[a[i].x];
sort(a+1,a+k+1,cmp);
bool tf=1;
for (int i=1;i<=k-1;i++) {
int x=a[i].x,y=a[i+1].x;
while (dep[x]>dep[y]) {
x=fa[x][lg[dep[x]-dep[y]]-1];
}
if (x!=y) {
tf=0;
break;
}
}
if (tf) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
} ————————————————————
2022.10.20
1.AT_dp_u Grouping
一道状态压缩DP……
参考的一份题解
除了枚举子集，其它的都没想到（悲）
这种题的预处理其实也算一个小难点，要特别注意。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=(1<<17)+5;
int n,a[233][233],val[N],dp[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cin>>a[i][j];
for (int i=1;i<(1<<n);i++)
for (int j=1;j<=n;j++)
for (int k=1;k<j;k++)
if ((1<<(k-1)&i)&&((1<<(j-1))&i))
val[i]+=a[j][k];
for (int i=1;i<(1<<n);i++) {
dp[i]=val[i];
for (int j=i&(i-1);j;j=i&(j-1)) {
dp[i]=max(dp[i],dp[i^j]+dp[j]);
}
}
cout<<dp[(1<<n)-1];
return 0;
}————————————
2.P2986 [USACO10MAR] Great Cow Gathering G
一道换根DP……
算是独立推出来了。
不述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int n,sum,tot,dp[N],c[N],head[N],dep[N],siz[N];
struct qwq{int to,hext,w;}e[N<<1];
void add(int x,int y,int z) {
e[++tot].hext=head[x];
e[tot].to=y;
e[tot].w=z;
head[x]=tot;
}
void dfs(int x,int fath) {
siz[x]=c[x];
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dep[v]=dep[x]+e[i].w;
dfs(v,x);
siz[x]+=siz[v];
}
}
void DFS(int x,int fath) {
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dp[v]=dp[x]+(sum-siz[v])*e[i].w-siz[v]*e[i].w;
DFS(v,x);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) cin>>c[i],sum+=c[i];
for (int i=1;i<=n-1;i++) {
int x,y,z;
cin>>x>>y>>z;
add(x,y,z),add(y,x,z);
}
dfs(1,0);
for (int i=2;i<=n;i++) dp[1]+=(dep[i])*c[i];
DFS(1,0);
int minn=dp[1];
for (int i=2;i<=n;i++) minn=min(minn,dp[i]);
cout<<minn;
return 0;
}————————————
3.P1801 黑匣子
一道对顶堆的题目。
反思一下为什么题解的代码比自己写的简单明了好多（emmmm）
以下放上参考题解后的代码。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int a[N],u[N],m,n;
priority_queue <int> q1;
priority_queue <int,vector<int>,greater<int> > q2;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>m>>n;
for (int i=1;i<=m;i++) cin>>a[i];
for (int i=1;i<=n;i++) cin>>u[i];
int j=0;
for (int i=1;i<=n;i++) {
while (j<u[i]) {
j++;
q1.push(a[j]);
q2.push(q1.top());
q1.pop();
}
cout<<q2.top()<<endl;
q1.push(q2.top());
q2.pop();
}
return 0;
}————————————
4.P2658 汽车拉力比赛
一道二分 + bfs ……
要点:
//!!!处，当bfs时，vis一定要在入队时就去判有没有更新并将标记数组更新，而不要等出队时再判（dfs时可以随意），不然会导致TLE或MLE（感谢cxy的讲解）……
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
bool vis[N][N];
int n,m,sx,sy,b[N][N],a[N][N];
queue <pair<int,int> > q;
bool check(int p) {
memset(vis,0,sizeof(vis));
while (!q.empty()) q.pop();
q.push({sx,sy}); vis[sx][sy]=1;
while (!q.empty()) {
int x=q.front().first,y=q.front().second;
q.pop();
for (int i=0;i<4;i++) {
int nx=x+dx[i],ny=y+dy[i];
if (nx<=0||nx>n||ny<=0||ny>m) continue;
if (vis[nx][ny]) continue;
if (abs(a[nx][ny]-a[x][y])>p) continue;
q.push({nx,ny});
vis[nx][ny]=1; //!!!
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (b[i][j]&&(!vis[i][j])) return 0;
return 1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
cin>>a[i][j];
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
cin>>b[i][j];
if (b[i][j]) sx=i,sy=j;
}
int l=0,r=1e9+1;
while (l+1<r) {
int mid=(l+r)>>1;
if (check(mid)) r=mid;
else l=mid+1;
}
if (check(l)) cout<<l<<endl;
else cout<<l+1<<endl;
return 0;
}————————————
5.P2325 [SCOI2005]王室联邦
参考的一份题解
emmmm尽量理解一下吧qwq
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,B,tot,cnt,sz,s[N],bel[N],rt[N],head[N];
struct qwq{int hext,to;}e[N<<1];
void dfs(int x,int fath) {
int cnr=sz;
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,x);
if (sz-cnr>=B) {
rt[++cnt]=x;
while (sz>cnr) bel[s[sz--]]=cnt;
}
}
s[++sz]=x;
}
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>B;
for (int i=1;i<=n-1;i++) {
int x,y; cin>>x>>y;
add(x,y); add(y,x);
}
dfs(1,0);
if (!cnt) rt[++cnt]=1;
while (sz) bel[s[sz--]]=cnt;
cout<<cnt<<endl;
for (int i=1;i<=n;i++) cout<<bel[i]<<" "; cout<<endl;
for (int i=1;i<=cnt;i++) cout<<rt[i]<<" "; cout<<endl;
return 0;
} ————————————
6.CF1399E1 Weights Division (easy version)
也算是一道独立完成的题（但是花了一个半小时（悲））。
要点：
//!!!处，要以将这个点减半而可以减少的权值来排序！（而不是这个点当前的权值，二者还是有一定区别的qwq）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int T,n,tot,s,leaf[N],head[N],dep[N],son[N],siz[N];
struct qwq{int hext,to,w;}e[N<<1];
void add(int x,int y,int z) {
e[++tot].hext=head[x];
e[tot].to=y;
e[tot].w=z;
head[x]=tot;
}
struct qaq{
int x,y,z;
friend bool operator <(qaq X,qaq Y) {
return (X.x<Y.x); //!!!
}
};
void dfs(int x,int fath) {
siz[x]=1;
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dep[v]=dep[x]+e[i].w;
dfs(v,x);
son[x]++;
siz[x]+=siz[v];
}
}
void DFS(int x,int fath) {
if (son[x]==0) leaf[x]=1;
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
DFS(v,x);
leaf[x]+=leaf[v];
}
}
int dep_max(int x,int y) {
if (dep[x]>dep[y]) return x;
else return y;
}
priority_queue <qaq > q;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>n>>s;
tot=0;
while (q.size()) q.pop();
for (int i=1;i<=n;i++) dep[i]=siz[i]=head[i]=son[i]=leaf[i]=0;
for (int i=1;i<=n-1;i++) {
int x,y,z;
cin>>x>>y>>z;
add(x,y,z); add(y,x,z);
}
dfs(1,0);
DFS(1,0);
int now=0,ans=0;
for (int i=1;i<=n;i++) {
if (son[i]==0) now+=dep[i];
}
for (int i=1;i<=tot;i+=2) {
int tmp=leaf[dep_max(e[i].to,e[i+1].to)]*e[i].w-leaf[dep_max(e[i].to,e[i+1].to)]*(e[i].w/2);
q.push((qaq){tmp,leaf[dep_max(e[i].to,e[i+1].to)],e[i].w});
}
while (now>s) {
int x=q.top().x,y=q.top().y,z=q.top().z;
q.pop();
ans++;
now-=x;
q.push((qaq){y*(z/2)-y*((z/2)/2),y,z/2});
}
cout<<ans<<endl;
}
return 0;
}————————————
7.CF1388C Uncle Bogdan and Country Happiness
还是比较水的（）……
要点：
dfs和DFS别用混！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int T,n,m,tot,head[N],siz[N],h[N],p[N],a[N];
bool tf;
struct qwq{int hext,to;}e[N<<1];
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int x,int fath) {
siz[x]=p[x];
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,x);
siz[x]+=siz[v];
}
}
void DFS(int x,int fath) {
int tmp=0;
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
tmp+=a[v];
DFS(v,x); //DFS!!!
}
if (tmp>a[x]) tf=0;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
tot=0;
cin>>n>>m;
for (int i=1;i<=n;i++) siz[i]=head[i]=0;
for (int i=1;i<=n;i++) cin>>p[i];
for (int i=1;i<=n;i++) cin>>h[i];
for (int i=1;i<=n-1;i++) {
int x,y;
cin>>x>>y;
add(x,y),add(y,x);
}
dfs(1,0);
tf=1;
for (int i=1;i<=n;i++) {
if ((siz[i]+h[i])&1) {
tf=0;
break;
}
}
for (int i=1;i<=n;i++) {
a[i]=(siz[i]+h[i])/2;
if (a[i]<0||siz[i]-a[i]<0) {
tf=0;
break;
}
}
DFS(1,0);
if (tf) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}————————————
8.P2017 [USACO09DEC]Dizzy Cows G
参考的一份题解
复习时努力理解一下吧（）……
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=300005;
int n,m1,m2,tot,head[N],ru[N];
struct qwq{int to,hext,w,from;}e[N];
queue <int> q;
void add(int x,int y,int z) {
e[++tot].hext=head[x];
e[tot].to=y;
e[tot].from=x;
e[tot].w=z;
head[x]=tot;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m1>>m2;
for (int i=1;i<=m1;i++) {
int x,y; cin>>x>>y;
add(x,y,0); ru[y]++;
}
for (int i=1;i<=n;i++)
if (ru[i]==0) q.push(i);
if (tot%2==0) tot++;
for (int i=1;i<=m2;i++) {
int x,y; cin>>x>>y;
add(x,y,1); add(y,x,1);
}
while (!q.empty()) {
int u=q.front(); q.pop();
for (int i=head[u];i;i=e[i].hext) {
int v=e[i].to;
if (e[i].w==0) {
ru[v]--;
if (ru[v]==0) q.push(v);
}
}
for (int i=head[u];i;i=e[i].hext) {
if (e[i].w==1) e[i^1].w=2;
}
}
for (int i=1;i<=tot;i++)
if (e[i].w==1) cout<<e[i].from<<" "<<e[i].to<<endl;
return 0;
}————————————
9.CF767C Garland
参考的一份题解
要点：
//!!!处是此题的关键步骤！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000006;
int fa[N],w[N],head[N],a[N],val[N];
int n,cnt,gen,tot,sum,tf,rec;
struct qwq{int hext,to,w;}e[N<<1];
void add(int x,int y,int z) {
e[++tot].hext=head[x];
e[tot].to=y;
e[tot].w=z;
head[x]=tot;
}
void dfs(int x,int fath) {
val[x]=w[x];
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,x);
val[x]+=val[v];
}
if (val[x]==sum/3) a[++cnt]=x,val[x]=0; //!!!
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) {
cin>>fa[i]>>w[i];
sum+=w[i];
}
if (sum%3!=0) {
cout<<-1<<endl;
return 0;
}
for (int i=1;i<=n;i++) {
if (fa[i]==0) gen=i;
else {
add(fa[i],i,w[i]);
add(i,fa[i],w[i]);
}
}
dfs(gen,0);
if (cnt>2) cout<<a[1]<<" "<<a[2]<<endl;
else cout<<-1<<endl;
return 0;
}————————————
10.P5092 [USACO04OPEN] Cube Stacking
一道很基础的并查集（类似银河英雄传说）。
但是还是没有独立写出来（悲）（实现时还是出现了一些细节上的问题）。
复习时重点理解一下（其实难度肯定不到蓝的）
参考的一份题解
要点见注释。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,Q,fa[N],siz[N],pre[N];
int find(int x) {
if (fa[x]==x) return x;
int fx=find(fa[x]);
pre[x]+=pre[fa[x]];
return fa[x]=fx;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>Q;
n=30000;
for (int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
while (Q--) {
char ch; cin>>ch;
if (ch=='M') {
int x,y;
cin>>x>>y;
int fx=find(x),fy=find(y);
if (fx==fy) continue;
fa[fx]=fy;
pre[fx]+=siz[fy];
siz[fy]+=siz[fx];
siz[fx]=0;
}
else {
int x;
cin>>x;
int fx=find(x); //询问前需要先将权值下传
cout<<pre[x]<<endl;
}
}
return 0;
}————————————
11.CF41D Pawn
也算是一道独立完成的……
要点：
-
//!!处，仔细看题，读入的话要翻转一下！ -
//!!!处，记得将dp初始化为-1（为了防止出现全0的a[i][j]然后输出无解（其实这个情况自己做的时候是想到了的，只不过以为将ans设为-1就可以了，实则如果不这样做根本走不到底））
#include <bits/stdc++.h>
#define int long long
using namespace std;
pair<int,int> pre[103][103][15];
int qwq,n,m,k,a[103][103],dp[103][103][15];
bool b[103][103][15];
string st;
void dfs(int x,int y,int p) {
if (x==1) {
cout<<y<<endl;
return ;
}
int nx=pre[x][y][p].first,ny=pre[x][y][p].second;
dfs(nx,ny,(p%(k+1)-a[x][y]%(k+1)+(k+1))%(k+1));
if (ny==y-1) {
st+='R';
}
else {
st+='L';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>k;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
char ch; cin>>ch;
a[n-i+1][j]=ch-'0'; //!!
}
}
memset(dp,-1,sizeof(dp)); //!!!
for (int i=1;i<=m;i++) dp[1][i][a[1][i]%(k+1)]=a[1][i],b[1][i][a[1][i]%(k+1)]=1;
for (int i=2;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (j!=1) {
for (int p=0;p<=k;p++) {
if (b[i-1][j-1][p]) {
if (dp[i][j][(p+a[i][j])%(k+1)]<dp[i-1][j-1][p]+a[i][j]) {
dp[i][j][(p+a[i][j])%(k+1)]=dp[i-1][j-1][p]+a[i][j];
b[i][j][(p+a[i][j])%(k+1)]=1;
pre[i][j][(p+a[i][j])%(k+1)]={i-1,j-1};
}
}
}
}
if (j!=m) {
for (int p=0;p<=k;p++) {
if (b[i-1][j+1][p]) {
if (dp[i][j][(p+a[i][j])%(k+1)]<dp[i-1][j+1][p]+a[i][j]) {
dp[i][j][(p+a[i][j])%(k+1)]=dp[i-1][j+1][p]+a[i][j];
b[i][j][(p+a[i][j])%(k+1)]=1;
pre[i][j][(p+a[i][j])%(k+1)]={i-1,j+1};
}
}
}
}
}
}
int ans=-1;
for (int i=1;i<=m;i++)
if (b[n][i][0]) {
if (ans<dp[n][i][0]) ans=dp[n][i][0],qwq=i;
}
if (ans==-1) cout<<-1<<endl;
else {
cout<<ans<<endl;
dfs(n,qwq,0);
cout<<st<<endl;
}
return 0;
}————————————————————
2022.10.21
1. CF362C Insertion Sort
感觉还是有一定难度的……
参考的一份题解
一个从这道题中得出的小知识：
- 冒泡排序需要交换的次数就是逆序对的个数
#include <bits/stdc++.h>
using namespace std;
const int N=5003;
int a[N],L[N][N],M[N][N],n,ori;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) {
a[i]++;
for (int j=1;j<=n;j++) {
L[i][j]=L[i-1][j]+(a[i]<j);
M[i][j]=M[i-1][j]+(a[i]>j);
}
ori+=M[i][a[i]];
}
int ans=ori,ansk=0;
for (int i=1;i<=n;i++) {
for (int j=i+1;j<=n;j++) {
int p=ori+M[i-1][a[i]]-M[j-1][a[j]]-L[j-1][a[i]]+L[i][a[i]];
p+=M[i-1][a[j]]+M[j-1][a[i]]+L[j-1][a[j]]-L[i][a[j]];
if (ans>p) ans=p,ansk=1;
else if (ans==p) ansk++;
}
}
cout<<ans<<" "<<ansk<<endl;
return 0;
}————————————
2.P4305 [JLOI2011]不重复数字
用 unordered_map 可过。
不述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,T,a[N];
unordered_map <int,int> mp;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
mp.clear();
for (int i=1;i<=n;i++) {
mp[a[i]]++;
if (mp[a[i]]==1) cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}————————————
3.CF417D Cunning Gena
一道状压DP。
要点：
-
//!!处，inf要开得大一点！ -
//!!!处，对于显示器的处理：按需要的显示器数排序即可！（这一点自己是看了题解之后才知道的emmmm，不过这题其它的话应该就是很常规的了qwq）
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct qwq{int v,k,tot,z;}a[2333];
int que[233][233],n,m,B,ans,inf;
int dp[(1<<20)+5];
bool cmp(qwq x,qwq y) {
return x.k<y.k;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>B;
inf=2e9+7; inf*=inf; //!!
for (int i=1;i<=n;i++) {
cin>>a[i].v>>a[i].k>>a[i].tot;
int x=0;
for (int j=1;j<=a[i].tot;j++) {
cin>>que[i][j];
x=x+(1<<(que[i][j]-1));
}
a[i].z=x;
}
ans=inf;
sort(a+1,a+n+1,cmp); //!!!
for (int i=1;i<(1<<m);i++) dp[i]=inf;
for (int lim=1;lim<=n;lim++) {
for (int i=0;i<(1<<m);i++) {
dp[i|a[lim].z]=min(dp[i|a[lim].z],dp[i]+a[lim].v);
}
ans=min(ans,dp[(1<<m)-1]+a[lim].k*B);
}
if (ans==inf) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
————————————
4. CF985E Pencils and Boxes
参考的一份题解
有点类似双指针（？）
不过自己确实没有想到emmmmm
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
int n,k,d,p,a[N],f[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k>>d;
for (int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
f[0]=1; p=1;
for (int i=0;i<=n;i++) {
if (f[i]) {
p=max(p,i+k);
while (p<=n&&a[p]-a[i+1]<=d) {
f[p]=1;
p++;
}
}
}
if (f[n]) cout<<"YES";
else cout<<"NO";
return 0;
}————————————
5.CF374C Inna and Dima
参考的一份题解
记搜的思路应该是一开始就有了，不过在实现上还是出现了一点问题（还有就是一开始并不确定记搜是否能过）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1003;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int n,m,cnt,tot,id[N][N];
int a[N][N],head[N*N*4],dis[N*N];
bool vis[N*N],tf;
string st;
struct qwq{int hext,to;}e[N*N*4];
void dfs(int x) {
if (dis[x]) return ;
vis[x]=1; dis[x]=1;
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (vis[v]) {
tf=1;
vis[x]=0;
return ;
}
dfs(v);
if (tf) {
vis[x]=0;
return ;
}
dis[x]=max(dis[x],dis[v]+1);
}
vis[x]=0;
}
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=1;i<=n;i++) {
cin>>st;
for (int j=0;j<m;j++) {
if (st[j]=='D') a[i][j+1]=1;
if (st[j]=='I') a[i][j+1]=2;
if (st[j]=='M') a[i][j+1]=3;
if (st[j]=='A') a[i][j+1]=4;
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
id[i][j]=++cnt;
for (int x=1;x<=n;x++)
for (int y=1;y<=m;y++) {
for (int k=0;k<4;k++) {
int nx=x+dx[k],ny=y+dy[k];
if (nx<0||nx>n||ny<0||ny>m) continue;
if (a[x][y]+1==a[nx][ny]) add(id[x][y],id[nx][ny]);
if (a[x][y]==4&&a[nx][ny]==1) add(id[x][y],id[nx][ny]);
}
}
int ans=0;
tf=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
if (a[i][j]==1) {
dfs(id[i][j]);
if (tf) {
cout<<"Poor Inna!";
return 0;
}
if (dis[id[i][j]]>ans) ans=dis[id[i][j]];
}
}
ans/=4;
if (ans) cout<<ans;
else cout<<"Poor Dima!";
return 0;
}————————————
6.CF766D Mahmoud and a Dictionary
参考的一份题解
一道扩展域并查集……
这个的确是还没有接触过qwq……
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,m,Q,fa[N];
unordered_map <string,int> mp;
int find(int x) {
if (x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>Q;
for (int i=1;i<=n;i++) {
string st;
cin>>st;
mp[st]=i;
}
for (int i=1;i<=n;i++) fa[i]=i,fa[i+n]=i+n;
while (m--) {
int opt; cin>>opt;
string s1,s2; cin>>s1>>s2;
int x=mp[s1],y=mp[s2];
if (opt==1) {
if (find(x)==find(y+n)) {
cout<<"NO"<<endl;
}
else {
cout<<"YES"<<endl;
fa[find(x)]=find(y);
fa[find(x+n)]=find(y+n);
}
}
else {
if (find(x)==find(y)) {
cout<<"NO"<<endl;
}
else {
cout<<"YES"<<endl;
fa[find(x+n)]=find(y);
fa[find(x)]=find(y+n);
}
}
}
while (Q--) {
string s1,s2;
cin>>s1>>s2;
int x=mp[s1],y=mp[s2];
if (find(x)==find(y)) cout<<1<<endl;
else if (find(x)==find(y+n)) cout<<2<<endl;
else cout<<3<<endl;
}
return 0;
}————————————
7. CF245F Log Stream Analysis
今年2月时cxy模拟赛时的一道题……
赛时应该算是一道大模拟T1（然后赛时过了，但过不了原题）
现在终于查出来错在哪里了……
要点：
//!!!处，自己一开始把月份判错了emmmmmm
#include <bits/stdc++.h>
using namespace std;
struct qwq{
int yea;
int mon;
int da;
int hou;
int minut;
int sec;
int duru;
}a[100005],b;
int N,M,n;
string st;
bool shuzi(char ch) {
if (ch>='0' && ch<='9') return 1;
else return 0;
}
bool cmp(qwq x,qwq y) {
if (x.yea!=y.yea) return (x.yea<y.yea);
if (x.mon!=y.mon) return (x.mon<y.mon);
if (x.da!=y.da) return (x.da<y.da);
if (x.hou!=y.hou) return (x.hou<y.hou);
if (x.minut!=y.minut) return (x.minut<y.minut);
if (x.sec!=y.sec) return (x.sec<y.sec);
return (x.duru<y.duru);
}
bool rui(int x) {
if (x==2012) return 1;
else return 0;
}
int pd_mon(int x,int y) {
if (x==1||x==3||x==5||x==7||x==8||x==10||x==12) return 31;
if (x==4||x==6||x==9||x==11) return 30; //!!!
if (x==2 && rui(y)) return 29;
else return 28;
}
int bianli_mon(int x,int y,int nianx,int niany) {//x:former y:latter
//计算从nianx年x月的某一时刻到niany年y月的同一时刻所需要的时间
int res=0;
if (nianx==niany) {
for (int i=x;i<=y-1;i++)
res+=pd_mon(i,nianx);
return res;
}
if (nianx<niany) {
for (int i=x;i<=12;i++) res+=pd_mon(i,nianx);
for (int i=1;i<=y-1;i++) res+=pd_mon(i,niany);
return res;
}
return res;
}
int js(qwq x,qwq y){ //x:former y:latter
int tmp=0;
tmp=b.sec*(y.sec-x.sec)+b.minut*(y.minut-x.minut);
tmp+=b.hou*(y.hou-x.hou)+b.da*(y.da-x.da);
tmp+=bianli_mon(x.mon,y.mon,x.yea,y.yea)*b.da;
return tmp;
}
int main(){
cin>>N>>M;
b.sec=1,b.minut=60,b.hou=60*60,b.da=60*60*24;
int ii=0;
while (cin>>st) {
ii++;
a[ii].yea=2012;
a[ii].mon=(int)(st[5]-'0')*10+(int)(st[6]-'0');
a[ii].da=(int)(st[8]-'0')*10+(int)(st[9]-'0');
char c;
c=getchar();
getline(cin,st);
a[ii].hou=(int)(st[0]-'0')*10+(int)(st[1]-'0');
a[ii].minut=(int)(st[3]-'0')*10+(int)(st[4]-'0');
a[ii].sec=(int)(st[6]-'0')*10+(int)(st[7]-'0');
a[ii].duru=ii;
}
n=ii;
sort(a+1,a+n+1,cmp);
for (int i=M;i<=n;i++) {
if (js(a[i-M+1],a[i])<N) {
cout<<a[i].yea<<"-";
if (a[i].mon<10) cout<<"0"<<a[i].mon<<"-";
else cout<<a[i].mon<<"-";
if (a[i].da<10) cout<<"0"<<a[i].da<<" ";
else cout<<a[i].da<<" ";
if (a[i].hou<10) cout<<"0"<<a[i].hou<<":";
else cout<<a[i].hou<<":";
if (a[i].minut<10) cout<<"0"<<a[i].minut<<":";
else cout<<a[i].minut<<":";
if (a[i].sec<10) cout<<"0"<<a[i].sec<<endl;
else cout<<a[i].sec<<endl;
return 0;
}
}
printf("-1\n");
return 0;
}————————————
2022.10.23
1. AT_joi2015yo_a 水道料金 (Water Rate)
大约三年前尝试过的一道题，之后再想尝试就被过水隐藏了……
最近这题又开放了，所以就把它A一下。
要点：
- 换行！（不过这个似乎不是自己的问题，但是这题就是要换行才能过（悲））
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int x,a,b,c,n;
cin>>x>>a>>b>>c>>n;
int ans1=x*n;
int ans2=a+max(n-b,(int)0)*c;
cout<<min(ans1,ans2)<<endl;
return 0;
}————————————
2. CF1156B Ugly Pairs
一道很巧妙的构造题。
参考的一份题解
这个思路的确没想到。
要点：
//!!!处，还要考虑cnt1==0或者cnt2==0的情况……
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int a[N],a1[N],a2[N];
int T,n,cnt1,cnt2;
string st;
bool cmp(int x,int y) {
return x<y;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>st;
n=st.size();
for (int i=1;i<=n;i++) a[i]=st[i-1]-'a'+1;
sort(a+1,a+n+1,cmp);
cnt1=cnt2=0;
a1[1]=a2[1]='0'; //!!!
for (int i=1;i<=n;i++) {
if (a[i]&1) a1[++cnt1]=a[i];
else a2[++cnt2]=a[i];
}
if (abs(a1[cnt1]-a2[1])>1) {
for (int i=1;i<=cnt1;i++) cout<<(char)(a1[i]+96);
for (int i=1;i<=cnt2;i++) cout<<(char)(a2[i]+96);
}
else if (abs(a1[1]-a2[cnt2])>1) {
for (int i=1;i<=cnt2;i++) cout<<(char)(a2[i]+96);
for (int i=1;i<=cnt1;i++) cout<<(char)(a1[i]+96);
}
else cout<<"No answer";
cout<<endl;
}
return 0;
} ————————————————————
2022.10.23
提交 3.0k 了（好诶！）
1.P3373 【模板】线段树 2
重新修改了一下码风（）
虽然自己不擅长DS，但是这种基础的数据结构还是得掌握吧qwq
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000005;
struct qwq{int val,mul,add;}tree[N<<2];
int n,m,p,a[N];
int ls(int x) {return (x<<1);}
int rs(int x) {return (x<<1|1);}
void push_up(int rt) {
tree[rt].val=(tree[ls(rt)].val+tree[rs(rt)].val)%p;
}
void build(int rt,int l,int r) {
tree[rt].mul=1; tree[rt].add=0;
if (l==r) {
tree[rt].val=a[l];
return ;
}
int mid=(l+r)>>1;
build(ls(rt),l,mid);
build(rs(rt),mid+1,r);
push_up(rt);
}
void push_down(int rt,int l,int r) {
int mid=(l+r)>>1;
tree[ls(rt)].val=(tree[ls(rt)].val*tree[rt].mul+tree[rt].add*(mid-l+1))%p;
tree[rs(rt)].val=(tree[rs(rt)].val*tree[rt].mul+tree[rt].add*(r-mid))%p;
tree[ls(rt)].mul=(tree[ls(rt)].mul*tree[rt].mul)%p;
tree[rs(rt)].mul=(tree[rs(rt)].mul*tree[rt].mul)%p;
tree[ls(rt)].add=(tree[ls(rt)].add*tree[rt].mul+tree[rt].add)%p;
tree[rs(rt)].add=(tree[rs(rt)].add*tree[rt].mul+tree[rt].add)%p;
tree[rt].mul=1; tree[rt].add=0;
}
void update_jia(int rt,int l,int r,int nl,int nr,int k) {
if (l>nr||r<nl) return ;
if (nl<=l&&r<=nr) {
tree[rt].add=(tree[rt].add+k)%p;
tree[rt].val=(tree[rt].val+k*(r-l+1)%p)%p;
return ;
}
push_down(rt,l,r);
int mid=(l+r)>>1;
update_jia(ls(rt),l,mid,nl,nr,k);
update_jia(rs(rt),mid+1,r,nl,nr,k);
push_up(rt);
}
void update_cheng(int rt,int l,int r,int nl,int nr,int k) {
if (l>nr||r<nl) return ;
if (nl<=l&&r<=nr) {
tree[rt].mul=(tree[rt].mul*k)%p;
tree[rt].add=(tree[rt].add*k)%p;
tree[rt].val=(tree[rt].val*k)%p;
return ;
}
push_down(rt,l,r);
int mid=(l+r)>>1;
update_cheng(ls(rt),l,mid,nl,nr,k);
update_cheng(rs(rt),mid+1,r,nl,nr,k);
push_up(rt);
}
int query_jia(int rt,int l,int r,int nl,int nr) {
if (nr<l||r<nl) return 0;
if (nl<=l&&r<=nr) return tree[rt].val;
push_down(rt,l,r);
int mid=(l+r)>>1;
int tmp=(query_jia(ls(rt),l,mid,nl,nr)+query_jia(rs(rt),mid+1,r,nl,nr))%p;
return tmp;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>p;
for (int i=1;i<=n;i++) {
cin>>a[i];
}
build(1,1,n);
while (m--) {
int opt; cin>>opt;
if (opt==1) {
int x,y,k;
cin>>x>>y>>k;
update_cheng(1,1,n,x,y,k);
}
if (opt==2) {
int x,y,k;
cin>>x>>y>>k;
update_jia(1,1,n,x,y,k);
}
if (opt==3) {
int x,y;
cin>>x>>y;
int ans=query_jia(1,1,n,x,y);
cout<<ans<<endl;
}
}
return 0;
} ————————————
2. CF1742G Orray
一道还是比较水的贪心……
要点：
//!!!处，这句话别忘记！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int T,n,a[N],vis[N],ans[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>n;
for (int i=1;i<=n;i++) {
cin>>a[i]; vis[i]=0;
}
int now=0,cnt=0;
for (int j=30;j>=0;j--) {
int maxn=now,k=0;
if (now&(1<<j)) continue; //!!!
for (int i=1;i<=n;i++) {
if (a[i]&(1<<j)) {
if (maxn<(now|a[i])) {
maxn=now|a[i];
k=i;
}
}
}
if (k!=0) {
ans[++cnt]=k; vis[k]=1;
now=maxn;
}
}
for (int i=1;i<=cnt;i++) cout<<a[ans[i]]<<" ";
for (int i=1;i<=n;i++)
if (!vis[i]) cout<<a[i]<<" ";
cout<<endl;
}
return 0;
}————————————
3. CF1746D Paths on the Tree
参考的一份题解
一道赛时尝试了但最终还是没有 A 掉的 div2D ……
这个基本思路是贪心，但是自己一开始的贪心是错的……（在权值相同的子树的选择中可能会炸）
要点：
- 是将
dfs的值去贪心！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=400005;
struct qwq{int hext,to;}e[N];
int head[N],son[N],s[N];
int T,n,k,tot,ans,fa[N];
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int x,int fath) {
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,x);
son[x]++;
}
}
int DFS(int x,int fath,int now) {
ans+=now*s[x];
if (!son[x]) return s[x];
int qwq=now%son[x],tmp=0;
priority_queue <int> q;
for (int i=head[x];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
q.push(DFS(v,x,now/son[x]));
}
if (qwq) {
while (qwq--) {
ans+=q.top();
q.pop();
}
}
return q.top()+s[x];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>n>>k;
tot=0;
for (int i=1;i<=n;i++) son[i]=0;
for (int i=2;i<=n;i++) cin>>fa[i];
for (int i=1;i<=n;i++) cin>>s[i];
for (int i=2;i<=n;i++) {
add(fa[i],i);
}
dfs(1,0);
ans=0;
int ttt=DFS(1,0,k);
cout<<ans<<endl;
for (int i=1;i<=tot;i++) e[i].hext=e[i].to=0;
for (int i=1;i<=n;i++) head[i]=0;
}
return 0;
}————————————
4.P6565 [NOI Online #3 入门组] 最急救助
水题，不述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,ans;;
string name,st;
vector <string> vec;
int js(string s) {
int t=0;
for (int i=1;i<s.size()-1;i++)
if (s[i]=='o'&&s[i-1]=='s'&&s[i+1]=='s') t++;
return t;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>name;
cin>>st;
int tmp=js(st);
if (ans<tmp) {
ans=tmp;
vec.clear();
vec.push_back(name);
}
else if (ans==tmp) {
vec.push_back(name);
}
}
for (int i=0;i<vec.size();i++) cout<<vec[i]<<" ";cout<<endl;
cout<<ans<<endl;
return 0;
}————————————
5.P6566 [NOI Online #3 入门组] 观星
也是一道水题，不述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int dx[]={1,-1,1,-1,0,0,1,-1};
const int dy[]={1,-1,-1,1,1,-1,0,0};
const int N=2003;
int n,m,sum,ans,tot,col,a[N][N];
string st;
bool vis[N][N];
unordered_map <int,int> mp;
void dfs(int x,int y,int c) {
for (int i=0;i<8;i++) {
int nx=x+dx[i],ny=y+dy[i];
if (nx<1||nx>n||ny<1||ny>m) continue;
if (!a[nx][ny]) continue;
if (vis[nx][ny]) continue;
vis[nx][ny]=1;
sum++;
dfs(nx,ny,c);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=1;i<=n;i++) {
cin>>st;
for (int j=0;j<m;j++)
if (st[j]=='*') a[i][j+1]=1;
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (a[i][j]&&(!vis[i][j])) {
col++;
sum=1;
vis[i][j]=1;
dfs(i,j,col);
if (mp[sum]==0) tot++;
mp[sum]+=sum;
ans=max(ans,mp[sum]);
}
}
}
cout<<tot<<" "<<ans;
return 0;
}————————————
Codeforces Round #829 (Div. 2)
————————————
Codeforces Round #830 (Div. 2)
————————————————————
2022.10.24
1.P6293 [eJOI2017] 经验
今天模拟赛的T3……其实还是可做的（不过自己赛时的思路还是不够清晰，没有想到这个递增递减的性质）。
思路：
-
我们可以得知，我们剖成的树链一定是递增或者递减的（如果不是这样的话，一定能将其剖开使得贡献不减）
-
所以我们可以来进行 树形DP ：
f[i][0]表示i所在的链为从下往上递增，其子树可以达到的最大经验值（f[i][1]同理）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,tot,son[N],fa[N],head[N],w[N],f[N][2];
struct edge{
int hext,to;
}e[N];
void add(int x,int y) {
e[++tot].hext=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int u,int fath) {
int t=0;
for (int i=head[u];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
dfs(v,u),t+=max(f[v][0],f[v][1]);
}
f[u][0]=f[u][1]=t;
for (int i=head[u];i;i=e[i].hext) {
int v=e[i].to;
if (v==fath) continue;
if (w[v]<=w[u]) f[u][0]=max(f[u][0],t-max(f[v][0],f[v][1])+f[v][0]+abs(w[u]-w[v]));
if (w[v]>=w[u]) f[u][1]=max(f[u][1],t-max(f[v][0],f[v][1])+f[v][1]+abs(w[u]-w[v]));
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) {
cin>>w[i];
}
for (int i=1;i<=n-1;i++) {
int x,y; cin>>x>>y;
add(x,y); add(y,x);
}
dfs(1,0);
int ans=max(f[1][0],f[1][1]);
cout<<ans;
return 0;
}————————————
2.P7472 [NOI Online 2021 入门组] 吃豆人
参考的一份题解（主要关注重合的式子）
一道黄题，推式子推了半天还是没能推成（悲）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2003;
int n,a[N][N];
struct qwq{
int s,num;
}ans[N];
bool cmp(qwq x,qwq y) {
return x.s>y.s;
}
int js(int x,int y) {
int tmp=0;
if (x==n) {
for (int i=1;i<=n;i++) tmp+=a[i][n-i+1];
return tmp;
}
if (x==1) {
for (int i=1;i<=n;i++) tmp+=a[i][i];
return tmp;
}
while (x<n) {
x++,y++;
tmp+=a[x][y];
}
while (y<n) {
x--,y++;
tmp+=a[x][y];
}
while (x>1) {
x--,y--;
tmp+=a[x][y];
}
while (y>1) {
x++,y--;
tmp+=a[x][y];
}
return tmp;
}
int chonghe(int x,int y) { //重点关注！
if (x>y) swap(x,y);
if ((y-x)%2==1) return 0;
if (x==1&&y==n) return a[(n+1)/2][(n+1)/2];
if (x==1) return a[(x+y)/2][(x+y)/2]+a[(2*n-y+1)/2][(2*n-y+1)/2];
if (y==n) return a[(n-x)/2+1][(n+x)/2]+a[(n+x)/2][(n-x)/2+1];
int nx=(x+y)/2,ny=(y-x)/2+1;
int tmp=a[nx][ny]+a[ny][nx]+a[n+1-ny][n+1-nx]+a[n+1-nx][n+1-ny];
return tmp;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++)
cin>>a[i][j];
}
for (int i=1;i<=n;i++) {
ans[i].s=js(i,1);
ans[i].num=i;
}
sort(ans+1,ans+n+1,cmp);
if (chonghe(ans[1].num,ans[2].num)==0) {
cout<<ans[1].s+ans[2].s<<endl;
}
else {
int tmp=0;
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
tmp=max(tmp,ans[i].s+ans[j].s-chonghe(ans[i].num,ans[j].num));
cout<<tmp<<endl;
}
return 0;
}————————————
3.P7911 [CSP-J 2021] 网络连接
要点：
//!!!处，别忘记判这个！
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
string op,ad;
map <string,int> mp;
bool pipei(int x,int len) {
if (x==0&&len!=1) return 0;
if (x>0&&x<=9&&len!=1) return 0;
if (x>=10&&x<=99&&len!=2) return 0;
if (x>=100&&x<=999&&len!=3) return 0;
if (x>=1000&&x<=9999&&len!=4) return 0;
if (x>=10000&&x<=99999&&len!=5) return 0;
return 1;
}
bool check(string s) {
int tot1=0,tot2=0,tf=0;
for (int i=0;i<s.size();i++) {
if (s[i]=='.'&&(!tf)) tot1++;
else if (s[i]==':'&&(!tf)) {tf=1;tot2++;}
else if (tf&&(s[i]=='.'||s[i]==':')) return 0;
}
if (tot1!=3) return 0;
if (tot2!=1) return 0; //!!!
int len=0,x=0;
for (int i=0;i<s.size();i++) {
if (s[i]==':'||s[i]=='.') {
if (!pipei(x,len)) return 0;
if (x>255) return 0;
len=0,x=0;
}
else {
len++; x=x*10+s[i]-'0';
}
}
if (!pipei(x,len)) return 0;
if (x>65535) return 0;
return 1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) {
cin>>op>>ad;
if (!check(ad)) cout<<"ERR"<<endl;
else {
if (op[0]=='S') {
if (mp[ad]) cout<<"FAIL"<<endl;
else {cout<<"OK"<<endl;mp[ad]=i;}
}
else {
if (mp[ad]) cout<<mp[ad]<<endl;
else cout<<"FAIL"<<endl;
}
}
}
return 0;
}————————————
4.P7910 [CSP-J 2021] 插入排序
去年11月份的时候写过的一道题（不过没有A掉）……
其实没有那么难（毕竟是J组T2）……
要点：
//!!!处，记得倒序！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,Q,p[N];
struct qwq{int s,num;}a[N];
bool cmp(qwq x,qwq y) {
if (x.s==y.s) return x.num<y.num;
return x.s<y.s;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>Q;
for (int i=1;i<=n;i++) cin>>a[i].s;
for (int i=1;i<=n;i++) a[i].num=i;
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;i++) {
p[a[i].num]=i; //p[x]:表示原来的第x个元素在排序后的数组中所对应的位置
}
while (Q--) {
int tag,x,y;
cin>>tag;
if (tag==1) {
cin>>x>>y;
if (y>=a[p[x]].s) {
int k=n+1;
for (int i=1;i<=n;i++)
if (a[i].s>y||a[i].s==y&&a[i].num>x) {
k=i;
break;
}
a[p[x]].s=y;
k--;
qwq tmp=a[p[x]];
for (int i=p[x];i<=k-1;i++)
a[i]=a[i+1];
a[k]=tmp;
}
else {
int k=0;
for (int i=n;i>=1;i--)
if (a[i].s<y||a[i].s==y&&a[i].num<x) {
k=i;
break;
}
a[p[x]].s=y;
k++;
qwq tmp=a[p[x]];
for (int i=p[x];i>=k+1;i--) //!!!
a[i]=a[i-1];
a[k]=tmp;
}
for (int i=1;i<=n;i++) p[a[i].num]=i;
}
else {
cin>>x;
cout<<p[x]<<'\n';
}
}
return 0;
}————————————
5.P6476 [NOI Online #2 提高组] 涂色游戏
一道好题（数学题）……
确实没有想到qwq……
参考的一份题解
#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
int gcd(int a,int b){
if (b==0) return a;
return gcd(b,a%b);
}
int lcm(int a,int b) {
return a/gcd(a,b)*b;
}
signed main(){
scanf("%lld",&T);
while (T--) {
int p1,p2,k;
scanf("%lld%lld%lld",&p1,&p2,&k);
if (p1<p2) swap(p1,p2);
if (k==1) printf("No\n");
else if (p1==p2) printf("Yes\n");
else {
int n1=p2/gcd(p1,p2);
int n2=p1/gcd(p1,p2)-1;
if (n2%n1==0) n=n2/n1;
else n=n2/n1+1;
if (n<k) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}————————————
6.P5657 [CSP-S2019] 格雷码
现在终于能独立写出来了/xk
写的递归。
#include <bits/stdc++.h>
using namespace std;
unsigned long long n,k;
string s;
string js(unsigned long long x,int len) {
if (len==1) {
if (x==0) return "0";
else return "1";
}
if (x<(1ull<<(len-1))) return '0'+js(x,len-1);
else return '1'+js((1ull<<(len-1))-1ull+(1ull<<(len-1))-x,len-1ull);
//将 1ull<<(len-1) 拆分一下，防止爆 ull
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
string st=js(k,n);
cout<<st;
return 0;
}————————————————————
2022.10.25
1. CF1634C OKEA
以前赛时没有写出来的一题div2 C……
其实感觉还是有一定难度……
#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,n,m;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
while (T--) {
cin>>n>>m;
if (m==1) {
cout<<"YES"<<endl;
for (int i=1;i<=n;i++) cout<<i<<endl;
}
else if (n==1) {
cout<<"NO"<<endl;
}
else if (n%2==0) {
cout<<"YES"<<endl;
for (int i=1;i<=n;i++) {
for (int j=i;j<=n*m;j+=n) cout<<j<<" ";
cout<<endl;
}
}
else cout<<"NO"<<endl;
}
return 0;
}————————————
2.P2880 [USACO07JAN] Balanced Lineup G
一道线段树求区间最值。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
const int inf=1e9+7;
struct qwq{int minn,maxn;}tree[N<<2];
int n,q,a[N];
int ls(int x) {return x<<1;}
int rs(int x) {return x<<1|1;}
void push_up(int rt){
tree[rt].minn=min(tree[ls(rt)].minn,tree[rs(rt)].minn);
tree[rt].maxn=max(tree[ls(rt)].maxn,tree[rs(rt)].maxn);
}
int query_max(int rt,int l,int r,int nl,int nr) {
if (r<nl||l>nr) return 0;
if (nl<=l&&r<=nr) return tree[rt].maxn;
int mid=(l+r)>>1;
return max(query_max(ls(rt),l,mid,nl,nr),query_max(rs(rt),mid+1,r,nl,nr));
}
int query_min(int rt,int l,int r,int nl,int nr) {
if (r<nl||l>nr) return inf;
if (nl<=l&&r<=nr) return tree[rt].minn;
int mid=(l+r)>>1;
return min(query_min(ls(rt),l,mid,nl,nr),query_min(rs(rt),mid+1,r,nl,nr));
}
void build(int rt,int l,int r) {
if (l==r) {
tree[rt].minn=a[l];
tree[rt].maxn=a[l];
return ;
}
int mid=(l+r)>>1;
build(ls(rt),l,mid);
build(rs(rt),mid+1,r);
push_up(rt);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>q;
for (int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while (q--) {
int x,y;
cin>>x>>y;
int ans1=query_max(1,1,n,x,y),ans2=query_min(1,1,n,x,y);
cout<<ans1-ans2<<endl;
}
return 0;
}————————————
3.P5909 [CTSC2007]挂缀pendant
一道反悔贪心。
虽然最后还是写出来的，但其实感觉也还是有难度的。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
struct qwq{
int c,v;
}a[N];
int n,sum;
bool operator <(const qwq &x,const qwq &y) {
return x.v<y.v; //!!!
}
bool cmp(qwq x,qwq y) {
return x.c<y.c;
}
priority_queue <qwq> q;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) {
cin>>a[i].c>>a[i].v;
a[i].c+=a[i].v; //!!!
}
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;i++) {
if (sum+a[i].v<=a[i].c) {
q.push(a[i]);
sum+=a[i].v;
}
else if (q.top().v>a[i].v) {
sum-=q.top().v;
q.pop();
sum+=a[i].v;
q.push(a[i]);
}
}
cout<<q.size()<<endl<<sum<<endl;
while (q.size()) {
q.pop();
}
return 0;
}————————————
4.P2107 小Z的AK计划
以前写过的一题，但复习的时候发现当时能过就只是数据太水（思路很明显地错误，也不知道是怎么过的）
现在重构了一下，终于过了。
一道反悔贪心……
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
struct qwq{
int x;
int t;
}a[N];
priority_queue <int> q;
bool cmp(qwq xx,qwq yy) {
return xx.x<yy.x;
}
int n,m,tnow,ans,pre;
signed main(){
scanf("%lld%lld",&n,&m);
for (int i=1;i<=n;i++) {
scanf("%lld%lld",&a[i].x,&a[i].t);
}
sort(a+1,a+n+1,cmp);
int now=0;
for (int i=1;i<=n;i++) {
now+=(a[i].x-a[i-1].x);
if (now+a[i].t<=m) {
now+=a[i].t;
q.push(a[i].t);
}
else if (q.size()&&q.top()>a[i].t) {
int u=q.top(); q.pop();
now-=u;
q.push(a[i].t);
now+=a[i].t;
}
ans=max(ans,(int)q.size());
}
printf("%lld\n",ans);
return 0;
}————————————————————
2022.10.26
————————————————————
2022.10.27
————————————————————
2022.10.28
这几天在复习模板和以前的学习笔记……
两周的停课生活一晃而过……
希望明天能发挥出好成绩！
rp++
————————————————————