GDKOI TG Day1&2 游记

得分爆低的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
上一篇:s3打印管理器的安装和升级方法


下一篇:对于下发的文件进行爬取,减少人去下载的过程