NOIP 2022 VP 游寄
noip，非常伤心 /dk
初二，所以是 vp（？？
SM，晚了，有点尴尬
但是在下面也看到了其它学校的同学好多个，所以也没急
抱抱 yx 就进去了，学姐可爱
t1 不难的计数，30 min
诶，114 514（？
t2 猛冲 90min 不会，错解掉
t3 不会缩点，平方了，补了特殊性质
过了大样例，但是150 行（？？？
t4 最后几分钟，没时间 bf 了，有点可惜
考完非常自信
结果非常悲伤
笑死了 t1 数组 100*100，一个 0 值 50pts 呢
t3 大样例好好，甚至是链
哈哈，所以说不要相信大样例
寄了寄了寄了，我的平方 bf 寄了
所以是挂大分了
卧槽这个 t2 怎么数据分治啊，爬，没从这里想
我自己倒没什么，反正 vp
但是对我最重要的几个 oier
真就全部，全部，全部
t1 全部挂分了，全都是多测没清空
于是进不了队基本上，甚至有些退役
然后 EMO 了一个周末
下面是 sy 十分优美但错误的代码
#include<bits/stdc++.h>
#define int long long
#define MN 110
#define P 998244353
using namespace std;
int n, m, vc, vf, rc, rf;
int r[MN][MN], c[MN][MN];
int u[MN][MN], d[MN][MN];
char mp[MN][MN];
void mian() {
vc=vf=rc=rf=0;
memset(r,0,sizeof(r));
memset(c,0,sizeof(c));
memset(u,0,sizeof(u));
memset(d,0,sizeof(d));
memset(mp,0,sizeof(mp));
scanf("%lld%lld", &n, &m);
scanf("%lld%lld", &rc, &rf);
for(int i=1; i<=n; ++i)
scanf("%s", mp[i]+1);
for(int i=1; i<=n; ++i)
for(int j=m; j>=1; --j)
r[i][j]=(mp[i][j]=='1')?0:(r[i][j+1]+1);
for(int j=1; j<=m; ++j) {
for(int i=1; i<=n; ++i)
u[i][j]=(mp[i][j]=='1')?i:u[i-1][j];
for(int i=n; i>=1; --i)
d[i][j]=(mp[i][j]=='1')?0:(d[i+1][j]+1);
}
for(int j=1; j<=m; ++j) {
for(int i=1; i<=n; ++i) {
if(mp[i][j]=='1') continue;
c[i][j]=c[i-1][j]+r[i][j]-1;
if(u[i][j]<i-2) {
int qwq=c[i-2][j]*(r[i][j]-1)%P;
vc=(vc+qwq)%P, vf=(vf+qwq*(d[i][j]-1)%P)%P;
}
}
}
printf("%lld %lld\n", rc*vc%P, rf*vf%P);
}
signed main() {
freopen("plant.in","r",stdin);
freopen("plant.out","w",stdout);
int t, id;
scanf("%lld%lld", &t, &id);
while(t--) mian();
return 0;
}#include<bits/stdc++.h>
#define int long long
#define MN 4000010
using namespace std;
int n, m, k, a[MN], rt[MN];
int st[MN], top, tot;
int op[MN], s[MN], ss[MN];
int id[MN], cnt[MN];
int qp[MN], pos;
void mian() {
top=tot=pos=0;
memset(rt,0,sizeof(a));
memset(st,0,sizeof(a));
memset(id,0,sizeof(a));
memset(cnt,0,sizeof(a));
memset(qp,0,sizeof(a));
scanf("%lld%lld%lld", &n, &m, &k);
for(int i=1; i<=m; ++i)
scanf("%lld", a+i);
for(int i=1; i<=m; ++i) {
st[++top]=i;
while(top>=2&&a[st[top]]==a[st[top-1]])
rt[st[top-1]]=st[top], top-=2;
}
for(int i=1; i<=n; ++i) qp[++pos]=i;
for(int i=1; i<=m; ++i) {
if(rt[i]) {
for(int j=i; j<=rt[i]; ++j)
op[++tot]=1, s[tot]=1;
continue;
}
if(cnt[a[i]]) {
cnt[a[i]]--;
if(cnt[a[i]]==0)
qp[++pos]=id[a[i]];
}
else {
cnt[a[i]]=1;
id[a[i]]=qp[pos--];
}
op[++tot]=1, s[tot]=id[a[i]];
}
printf("%lld\n", tot);
for(int i=1; i<=tot; ++i) {
printf("%lld %lld", op[i], s[i]);
if(op[i]==2) printf(" %lld", ss[i]);
printf("\n");
}
}
signed main() {
freopen("meow.in","r",stdin);
freopen("meow.out","w",stdout);
int t;
scanf("%lld", &t);
while(t--) mian();
return 0;
}#include<bits/stdc++.h>
#define int long long
#define P 1000000007
#define MN 3001
#define INF 1000001
using namespace std;
int n, m, u, v, fp[4*INF];
int a[MN], b[MN], top;
int cnt[MN], fa[MN], ct[INF];
vector<int> to[INF], too[MN], chk[MN];
int getc(int p,int q) {
int res=0;
for(int i=1; i<=p; ++i) {
int qwq=fp[q-i+1+max(i-2,0ll)];
res=(res+(p-i+1)*qwq%P)%P;
}
return res;
}
void solve1() {
for(int i=1; i<=m; ++i)
scanf("%lld%lld", &u, &v);
printf("%lld", getc(n,m));
}
int dfs(int p,int lst) {
if(ct[p]==3) return 0;
if(to[p][0]!=lst)
return dfs(to[p][0],p)+1;
return dfs(to[p][1],p)+1;
}
void solve2() {
for(int i=1; i<=m; ++i) {
scanf("%lld%lld", &u, &v);
ct[u]++, ct[v]++;
to[u].push_back(v);
to[v].push_back(u);
}
int p=0;
for(int i=1; i<=n; ++i)
if(ct[i]==1) p=dfs(i,0);
int q=n-p, ans=getc(p,m);
int awa=fp[q+m]-fp[m];
awa=(awa%P+P)%P, ans=(ans+awa)%P;
int dk=fp[2*q]-fp[q];
for(int i=1; i<=p; ++i) {
int wcc=fp[p-1+p-i];
ans=(ans+dk*wcc%P)%P;
}
printf("%lld", ans);
}
void dfss(int p,int ix,int iy) {
cnt[p]=1;
for(int i=0; i<to[p].size(); ++i) {
if(to[p][i]==ix&&p==iy) continue;
if(p==ix&&to[p][i]==iy) continue;
if(cnt[to[p][i]]==0) dfss(to[p][i],ix,iy);
}
}
int isok() {
for(int i=1; i<=n; ++i)
if(cnt[i]==0) return 1;
return 0;
}
int get(int p) {
if(fa[p]==p) return p;
return fa[p]=get(fa[p]);
}
void mkta(int p,int lst) {
a[++top]=p;
for(int i=0; i<too[p].size(); ++i)
if(too[p][i]!=lst) mkta(too[p][i],p);
}
void solve3() {
int ans=0;
for(int i=1; i<=m; ++i) {
scanf("%lld%lld", &u, &v);
to[u].push_back(v);
to[v].push_back(u);
}
for(int i=1; i<=n; ++i) {
for(int j=0; j<to[i].size(); ++j) {
memset(cnt,0,sizeof(cnt));
dfss(1,i,to[i][j]);
chk[i].push_back(isok());
}
}
for(int i=1; i<=n; ++i) fa[i]=i;
for(int i=1; i<=n; ++i)
for(int j=0; j<to[i].size(); ++j) {
if(chk[i][j]) continue;
fa[get(i)]=get(to[i][j]);
}
memset(cnt,0,sizeof(cnt));
for(int i=1; i<=n; ++i) cnt[get(i)]++;
for(int i=1; i<=n; ++i)
for(int j=0; j<to[i].size(); ++j)
if(chk[i][j]) {
int ix=get(i), iy=get(to[i][j]);
too[ix].push_back(iy);
}
int kyt=0;
for(int i=1; i<=n; ++i)
if(too[i].size()==1)
{ kyt=i; break; }
mkta(kyt,0);
for(int i=1; i<=top; ++i) {
a[i]=cnt[a[i]], b[i]=b[i-1]+a[i];
int sy=fp[a[i]+m]-fp[m];
sy=(sy%P+P)%P, ans=(ans+sy)%P;
}
for(int i=1; i<=top; ++i)
for(int j=i+1; j<=top; ++j) {
int nh=fp[a[i]]-1;
int sz=fp[a[j]]-1;
int nf=fp[b[j-1]-b[i]+m-j+i];
int hy=(nh*sz%P)*nf%P;
ans=(ans+hy)%P;
}
printf("%lld", ans);
}
signed main() {
freopen("barrack.in","r",stdin);
freopen("barrack.out","w",stdout);
scanf("%lld%lld", &n, &m);
fp[0]=1;
for(int i=1; i<=n+m; ++i)
fp[i]=fp[i-1]*2%P;
if(m==n-1) solve1();
else if(m==n) solve2();
else solve3();
return 0;
}