得分爆低的2天
前言
这2天彻底凉了,Day1 10pts(2题解法假了,就作死),Day2 60pts(纯暴力,t1不会直接爆0),我是不是该AFO水洛谷线段树了?
2天的t3全是原题,还有Day1 t1,Day2 t1,t2 剧毒
2天t3全manacher,亲切问候出题人
SSL初一物品栏:
(之前出现过的物品现在不再重复出现)
一人一份盒饭(真香,WCR嫖了聪爷一碗汤&黄瓜)
SSL初一成就栏:
(觉得成就出现一次就够了,所以不写了)
SSL初一得分栏:
WJ:180pts
MYD:145pts
WCR:70pts(论算法假了有多惨)
KYX:10pts(这巨爷Day2 t2 用并查集,%%%得分不出所料,zero)
LYW:0pts
Day 1
[WJ早起,rp++]
[WCR四处游荡,rp=rand()]
T1
其实就是贪心,为毛我考场写了bfs……
ACcode:
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,head[100001],bian[200001][2],tot=1,x,y,m,u=0,s;
struct f{
int to,net;
} a[400001];
bool yo[100001];
void add(int x,int y)
{
a[tot].to=y;
a[tot].net=head[x];
head[x]=tot;
tot++;
return;
}
int main()
{
freopen("cut.in","r",stdin);
freopen("cut.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
yo[1]=1;
for (int j=head[1];j;j=a[j].net) bian[a[j].to][0]++;
printf("%d ",yo[1]);
for (int i=2;i<=n;i++)
{
if (bian[i][0]>bian[i][1]) yo[i]=0;
else yo[i]=1;
for (int j=head[i];j;j=a[j].net) bian[a[j].to][1-yo[i]]++;
printf("%d ",yo[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}
别问我T2~T4在哪,咕掉了,那几题对初一不友好
Day 2
[WCR今日犯困,rp=rand()%10]
¥晚间盒饭活动开始,有概率增加rp¥
WCR嫖聪爷黄瓜,
r
p
∗
=
10
rp*=10
rp∗=10
LYW与初三巨爷吃饭,
r
p
+
+
rp++
rp++
KYX,WJ面对面吃饭,
K
Y
X
r
p
=
W
J
r
p
=
(
K
Y
X
r
p
+
W
J
r
p
)
/
2
KYXrp=WJrp=(KYXrp+WJrp)/2
KYXrp=WJrp=(KYXrp+WJrp)/2
MYD与初二MYC吃饭,
r
p
=
s
q
r
(
r
p
)
rp=sqr(rp)
rp=sqr(rp)
WCR4处闲逛,
r
p
/
=
3
rp/=3
rp/=3
T1
恶心的期望dp,还有乘法逆元,考场直接放弃(图论选手的悲哀)
后来的ACcode:
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,x[1000001],y[1000001],f[1000001];
pair<int,int> exgcd(int a,int b)
{
if(b==0)return pair<int,int>(1,0);
pair<int,int> tmp=exgcd(b,a%b);
return pair<int,int>(tmp.second,tmp.first-a/b*tmp.second);
}
int ff(int x)
{
pair<int,int> tmp=exgcd(x,998244353);
return (tmp.first%998244353+998244353)%998244353;
}//致命扩欧
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);
if (n==0)
{
printf("1");
fclose(stdin);
fclose(stdout);
return 0;
}
for (int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]);
f[0]=y[0]*ff(x[0])%998244353;
for (int i=1;i<n;i++) f[i]=(f[i-1]-f[i-1]*x[i]*ff(y[i])%998244353+1)%998244353*y[i]%998244353*ff(x[i])%998244353;//致命dp
long long ans=0;
for (int i=0;i<n;i++) ans=(ans+f[i])%998244353;//毁童年破题
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
T2
暴力20pts可还行,下面是由TJH和聪爷帮忙完善的ACcode:
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
int n,m,a[200011],b[400011],c[400011],v=1,x=1,y,z;
void Quant(int x,int L,int R,int l,int r)//区间修改
{
if (L==l&&r==R)
{
b[x]+=v;
if (b[x]!=0) c[x]=R-l+1;//长度
else if (L==R) c[x]=0;
else c[x]=c[x*2]+c[x*2+1];
return;
}
int mid=(L+R)>>1;
if (r<=mid) Quant(x*2,L,mid,l,r);
else if (l>mid) Quant(x*2+1,mid+1,R,l,r);
else Quant(x*2,L,mid,l,mid),Quant(x*2+1,mid+1,R,mid+1,r);
if (b[x]!=0) c[x]=R-L+1;
else c[x]=c[x*2]+c[x*2+1];
return;
}
int Ask(int x,int L,int R,int l,int r)//询问最长距离
{
if (b[x]!=0) return r-l+1;
if (L==l&&r==R) return c[x];
int mid=(L+R)>>1;
if (r<=mid) return Ask(x*2,L,mid,l,r);
if (l>mid) return Ask(x*2+1,mid+1,R,l,r);
return Ask(x*2,L,mid,l,mid)+Ask(x*2+1,mid+1,R,mid+1,r);
}
int main()
{
freopen("island.in","r",stdin);
freopen("island.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if (a[i]<i) Quant(1,1,n,a[i]+1,i);
}
while (m--)
{
scanf("%d",&x);
if (x==1)
{
scanf("%d%d",&y,&z);
v=-1;
if (a[y]<y) Quant(1,1,n,a[y]+1,y);
v=1;
a[y]=z;
if (a[y]<y) Quant(1,1,n,a[y]+1,y);
}
else
{
scanf("%d",&y);
int z=1,yy=y;
while (z<=yy)
{
int mid=(z+yy)>>1;
if (Ask(1,1,n,mid,y)<y-mid+1) z=mid+1;
else yy=mid-1;//二分答案
}
printf("%d\n",yy);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
t3t4咕了,疯子出题人又是manacher又是dp,非人哉
后记
AC与正解相干,而分数与我退相干。 | ——WCR |
---|