NOIP 2023
phigy
·
·
个人记录
Day 1
T1
喜提 $3s$。 简单修改 $1$ 小时后通过。/lh
cpp 无法释放 fc，cmd 亦无法释放 fc。
炸裂。
只能大眼观察了。
```cpp
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define MAXN 3005
inline int read()
{
int f=1,x=0;
char c=getchar();
while(!isdigit(c)) {if(c=='-') {f=-1;} c=getchar();}
while(isdigit(c)) {x=x*10+c-'0';c=getchar();}
return f*x;
}
int n,m;
char c[MAXN][MAXN];
char c1[MAXN],c2[MAXN];
char now[MAXN],res[MAXN];
void srt(char s[MAXN])
{
int i,j;
int t[26]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
for(i=1;i<=m;i++)
{
t[s[i]-'a']++;
}
for(i=1,j=0;i<=m;i++)
{
while(t[j]==0)j++;
t[j]--;
s[i]=j+'a';
}
}
void rev(char s[MAXN])
{
int i;
for(i=1;i*2<=m;i++)
{
swap(s[i],s[m-i+1]);
}
}
int cmp(char s1[MAXN],char s2[MAXN])
{
int i;
for(i=1;i<=m;i++)
{
if(s1[i]<s2[i])
{
return 1;
}
if(s2[i]<s1[i])
{
return 2;
}
}
return 0;
}
void cpy(char s1[MAXN],char s2[MAXN])
{
int i;
for(i=1;i<=m;i++)
{
s1[i]=s2[i];
}
}
signed main()
{
freopen("dict.in","r",stdin);
freopen("dict.out","w",stdout);
int i;
n=read(),m=read();
for(i=1;i<=m;i++)
{
c1[i]=c2[i]='z'+1;
}
for(i=1;i<=n;i++)
{
cin>>(c[i]+1);
cpy(now,c[i]);
srt(now);
rev(now);
if(cmp(now,c1)==1)
{
cpy(c2,c1);
cpy(c1,now);
}
else if(cmp(now,c2)==1)
{
cpy(c2,now);
}
}
for(i=1;i<=n;i++)
{
if(cmp(c[i],c1)==0)
{
cpy(now,c2);
}
else
{
cpy(now,c1);
}
cpy(res,c[i]);
srt(res);
if(cmp(res,now)==1)
{
cout<<1;
}
else
{
cout<<0;
}
}
return 0;
}
```
### T2
easy，忽略双向边，直接无脑释放 `2-sat`。 $1$ 小时后通过。
`dev` 栈空间扩大失败，炸裂。
启动 `NOI-linux` 直接运行，通过样例四。
忘记 `diff` 尝试使用 `fc` 失败。
```cpp
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 200005
inline int read()
{
int f=1,x=0;
char c=getchar();
while(!isdigit(c)) {if(c=='-') {f=-1;} c=getchar();}
while(isdigit(c)) {x=x*10+c-'0';c=getchar();}
return f*x;
}
int C,T;
int n,m;
int a[MAXN];//我们认定 n+1,2,3 为 TUF
int rev(int x) {if(x>n) {return n+4-(x-n);} return -x;}///我有特殊取反技巧
struct edge {int to,next,dis;} e[MAXN*10];///我们认为 T 是 x F 是 x+n
int cnt,head[MAXN*2];
void add(int x,int y,int z) {cnt++;e[cnt].to=y;e[cnt].dis=z;e[cnt].next=head[x];head[x]=cnt;}/// 1 + 0 -
void add(int x,int y) {cnt++;e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt;}
int vis[MAXN];
int ans[MAXN];
void dfs(int x)
{
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(!ans[v]&&!vis[v])
{
ans[v]=e[i].dis?ans[x]:rev(ans[x]);
dfs(v);
}
}
}
int dfx,dfn[MAXN*2],low[MAXN*2],book[MAXN*2];
int st[MAXN*2],tot;
int col,scc[MAXN*2];
void tarjan(int x)
{
dfn[x]=low[x]=++dfx;
st[++tot]=x;
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])///不记得力
{
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x])
{
col++;
while(st[tot]!=x) {scc[st[tot]]=col;vis[st[tot]]=0;tot--;}
scc[st[tot]]=col;vis[st[tot]]=0;tot--;
}
}
void clear()
{
memset(ans,0,sizeof(ans));
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(head));
memset(low,0,sizeof(head));
memset(scc,0,sizeof(scc));
memset(book,0,sizeof(book));
cnt=0;
dfx=0;
tot=0;
col=0;
}
signed main()
{
freopen("tribool.in","r",stdin);
freopen("tribool.out","w",stdout);
int i;
C=read(),T=read();
while(T--)
{
n=read(),m=read();
for(i=1;i<=n;i++) {a[i]=i;}
for(i=1;i<=m;i++)
{
char op;
cin>>op;
if(op=='+') {int x=read(),y=read();a[x]=a[y];}
if(op=='-') {int x=read(),y=read();a[x]=rev(a[y]);}
if(op=='T') {int x=read();a[x]=n+1;}
if(op=='U') {int x=read();a[x]=n+2;}
if(op=='F') {int x=read();a[x]=n+3;}
}
for(i=1;i<=n;i++)
{
if(a[i]<=n)
{
if(a[i]>0) {add(i,a[i],1);add(a[i],i,1);}
else {add(i,-a[i],0);add(-a[i],i,0);}
}
else {ans[i]=a[i];}
}
for(i=1;i<=n;i++) {if(ans[i]&&vis[i]==0) {dfs(i);}}
memset(head,0,sizeof(head));
cnt=0;
for(i=1;i<=n;i++)
{
if(a[i]<=n)
{
if(a[i]>0) {add(i,a[i]);add(a[i],i);add(i+n,a[i]+n);add(a[i]+n,i+n);}
else {add(i+n,-a[i]);add(-a[i],i+n);add(i,-a[i]+n);add(-a[i]+n,i);}
}
}
for(i=1;i<=2*n;i++) {if(!dfn[i]) {tarjan(i);}}
for(i=1;i<=n;i++) {if(scc[i]==scc[i+n]) {ans[i]=n+2;}}
int res=0;
for(i=1;i<=n;i++) {if(ans[i]==n+2) {res++;}}
cout<<res<<endl;
clear();
}
return 0;
}
```
### T3
简单写个 $35$ 卡在 $1.2s$ 卡常半小时，`dev` 出现编译运行 `exe` 不匹配症状，可怕，启动 `NOI-linux` 直接运行，卡进 $1.1s$ ，去做 T4。
T4 做完想起来没开 O2，启动 O2，不用卡了。
八连通，有点不多的想法，但是再见。
```cpp
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define MAXN 2005
#define MAXC 2005
inline void read(int &x)
{
x=0;
char c=getchar();
while(!isdigit(c)) {c=getchar();}
while(isdigit(c)) {x=x*10+c-'0';c=getchar();}
}
int C,n,m,q;
int X[MAXN],Y[MAXN];
int a[MAXN],b[MAXN];
bool f[MAXC][MAXC],g[MAXC][MAXC];///X>Y X<Y
bool solvef()
{
f[0][1]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=(a[i]>b[j])&(f[i-1][j]|f[i][j-1]|f[i-1][j-1]);
}
}
return f[n][m];
}
bool solveg()
{
g[0][1]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
g[i][j]=(a[i]<b[j])&(g[i-1][j]|g[i][j-1]|g[i-1][j-1]);
}
}
return g[n][m];
}
inline bool solve()
{
return (a[1]>b[1]?solvef():(a[1]<b[1]?solveg():0));
}
signed main()
{
freopen("expand.in","r",stdin);
freopen("expand.out","w",stdout);
int i;
read(C),read(n),read(m),read(q);
for(i=1;i<=n;i++) {read(X[i]);a[i]=X[i];}
for(i=1;i<=m;i++) {read(Y[i]);b[i]=Y[i];}
putchar((char)(solve()+'0'));
int kx,ky;
while(q--)
{
read(kx),read(ky);
for(i=1;i<=n;i++) {a[i]=X[i];}
for(i=1;i<=m;i++) {b[i]=Y[i];}
int p;
while(kx--) {read(p);read(a[p]);}
while(ky--) {read(p);read(b[p]);}
putchar((char)(solve()+'0'));
}
return 0;
}
```
### T4
T2 写完后看了一眼，感觉 easy 线段树 DP。
T3 写完没卡常还剩一个小时。
先写个 $36$ 分 DP。
小孩子不懂事， T3 卡着玩，卡了半小时启动 O2。
然后就再见。
```cpp
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 3005
#define ll long long
inline int read()
{
int f=1,x=0;
char c=getchar();
while(!isdigit(c)) {if(c=='-') {f=-1;} c=getchar();}
while(isdigit(c)) {x=x*10+c-'0';c=getchar();}
return f*x;
}
int C,T;
int n,m,k,d;
ll sum[MAXN][MAXN];
ll f[MAXN][MAXN];
signed main()
{
freopen("run.in","r",stdin);
freopen("run.out","w",stdout);
int i,j;
C=read(),T=read();
while(T--)
{
memset(sum,0,sizeof(sum));
memset(f,0,sizeof(f));
n=read(),m=read(),k=read(),d=read();
while(m--) {int x=read(),y=read(),v=read();sum[x][y]+=v;}
for(i=1;i<=n;i++) {for(j=1;j<=k;j++) {sum[i][j]+=sum[i][j-1];}}
for(i=1;i<=n;i++)
{
for(j=0;j<=k;j++)
{
f[i][0]=max(f[i][0],f[i-1][j]);
}
for(j=1;j<=k;j++)
{
f[i][j]=f[i-1][j-1]+sum[i][j]-d;
}
}
ll ans=0;
for(i=0;i<=k;i++) ans=max(ans,f[n][i]);
cout<<ans<<endl;
}
return 0;
}
```
## 后记
现役选手湖北只有外校会 T3。/cf