第一次做ZOJ月赛，罚时爆表
只做了B~H rank14
先看了A，A不会、、看B、、发现B很水，然后什么都没想就把B码掉了
B1A后发现自己是第一个过B的，别人都把F过了，于是看F
发现F是一道很老的题了、、AekdyCoin出的一道题，求高精度前L位，用对数保存、、然后精度就被怒卡了
然后叶队告诉了我一种高精度的概率做法，贴了个模版水过去了
然后看C，C很水，忘记多组数据，交了3遍、、
看D，D也很水，水也交了4遍
看E，这不是裸裸的最小割吗、、为什么还会WA、、
[sum of the remainder roads' value]/[the amount of removed roads]
英语不好能怪谁QAQ
然后做H、、又被自己的英语水平虐爆了、、not smaller than、、然后就缩了下点、、交了8次、、、
然后发现G是水题、、写完之后推A、、什么都没推出、、然后就结束了
A Another Recurrence Sequence
B Gears
有四种操作：连接两个齿轮，这两个齿轮方向相反；取出一个齿轮（与它相连的其他齿轮的关系不变）；询问两个齿轮的转动方向是否相同；询问一个齿轮所在连通块的齿轮总数。
Solution：并查集，删除时保留旧点，新建一个点作为这个点取出后的位置
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,m,i,j,k,tot,u,v,x,y;
int fa[1000005],size[1000005],id[1000005],dis[1000005];
char opt;
int get(int x)
{
if(fa[x]==x)return x;
get(fa[x]);
dis[x]+=dis[fa[x]];
fa[x]=fa[fa[x]];
return fa[x];
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;++i)fa[i]=id[i]=i,size[i]=1,dis[i]=0;
tot=n;
for(;m;--m)
{
opt=getchar();
while(opt!='L'&&opt!='D'&&opt!='Q'&&opt!='S')opt=getchar();
if(opt=='L')
{
scanf("%d%d",&u,&v);
u=id[u];v=id[v];
x=get(u);y=get(v);
if(x!=y)
{
fa[x]=v;
if(dis[u]%2==1)dis[x]=0;
else dis[x]=1;
size[y]+=size[x];
}
}
if(opt=='D')
{
scanf("%d",&u);
x=get(id[u]);
--size[x];
id[u]=++tot;
fa[tot]=tot;
dis[tot]=0;
size[tot]=1;
}
if(opt=='Q')
{
scanf("%d%d",&u,&v);
x=get(id[u]);
y=get(id[v]);
if(x==y)
{
if(dis[id[u]]%2!=dis[id[v]]%2)printf("Different\n");
else printf("Same\n");
}else printf("Unknown\n");
}
if(opt=='S')
{
scanf("%d",&u);
printf("%d\n",size[get(id[u])]);
}
}
}
}
C Consecutive Blocks
一个序列中删除几个数，使连续相同的数最多
Solution：把每种颜色提出单独做，维护一个队列贪心
#include <stdio.h>
#include <stdlib.h>
#include <map>
using namespace std;
map <int,int> C;
int n,m,c,i,j,k,ans;
int col[100005],son[100005],R[100005],tail[100005];
int q[100005],l,r;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
C.clear();
c=ans=0;
for(i=1;i<=n;++i)
{
scanf("%d",&col[i]);
if(!C[col[i]])C[col[i]]=++c;
col[i]=C[col[i]];
}
for(i=1;i<=n;++i)son[i]=tail[i]=R[i]=0;
for(i=1;i<=n;++i)
if(!son[col[i]])son[col[i]]=tail[col[i]]=i;
else R[tail[col[i]]]=i,tail[col[i]]=i;
for(i=1;i<=c;++i)
{
l=1;r=0;
for(j=son[i];j;j=R[j])
{
q[++r]=j;
while((q[r]-q[l]+1)-(r-l+1)>m)++l;
if(r-l+1>ans)ans=r-l+1;
}
}
printf("%d\n",ans);
}
}
D An Easy Game
两个01串，每次选m个位置取反，问k次后第一个串变成第二个串的方案数
Solution：f[i][j]记录操作i次有j个位置和目标串不同的方案数，利用组合数转移
#include <stdio.h>
#include <stdlib.h>
#define p 1000000009
using namespace std;
int n,K,m,i,j,k;
long long C[105][105];
long long f[105][105];
char s1[105],s2[105];
int main()
{
C[0][0]=1;
for(i=0;i<=100;++i)
for(j=0;j<=i;++j)
{
C[i][j]%=p;
C[i+1][j]+=C[i][j];
C[i+1][j+1]+=C[i][j];
}
while(scanf("%d%d%d",&n,&K,&m)!=EOF)
{
scanf("%s",s1+1);
scanf("%s",s2+1);
k=0;
for(i=1;i<=n;++i)if(s1[i]!=s2[i])++k;
for(i=0;i<=K;++i)
for(j=0;j<=n;++j)
f[i][j]=0;
f[0][k]=1;
for(i=0;i<K;++i)
for(j=0;j<=n;++j)
if(f[i][j])
for(k=0;k<=m&&k<=j;++k)
f[i+1][j-k+m-k]=(f[i+1][j-k+m-k]+f[i][j]*C[j][k]%p*C[n-j][m-k]%p)%p;
printf("%lld\n",f[K][0]);
}
}
E Romantic Value
个一些边，使p和q不连通，优先保证权值最小，再使割的边数最少
Solution：最小割，边的流量为(边权*1005+1)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define inf 0x7f7f7f7f
using namespace std;
int son[500000],next[500000],ed[500000],flow[500000];
int d[50000];
bool s[50000];
int n,m,u,v,c,i,j,k,tot,S,T;
int ans,sum;
inline void add(int u,int v,int f)
{
next[++tot]=son[u];son[u]=tot;ed[tot]=v;flow[tot]=f;
next[++tot]=son[v];son[v]=tot;ed[tot]=u;flow[tot]=f;
}
int find(int now,int Flow)
{
if (now==T) return Flow;
int tmp,w=0,w0,i;
for(i=son[now];i&&w<Flow;i=next[i])
if((flow[i])&&(d[now]+1==d[ed[i]])&&(w0=min(Flow-w,flow[i]))&&(tmp=find(ed[i],w0)))
flow[i]-=tmp,flow[i^1]+=tmp,w+=tmp;
if(!w)d[now]=inf;
return w;
}
inline void dinic(int S,int T)
{
int queue[50000],t1,t2,tmp,i;
while(true)
{
memset(s,true,sizeof(s));
queue[1]=S;t1=0;t2=1;s[S]^=1;
while(t1<t2&&s[T])
for(i=son[queue[++t1]];i;i=next[i])
if(flow[i]&&s[ed[i]])
queue[++t2]=tmp=ed[i],d[tmp]=d[queue[t1]]+1,s[tmp]^=1;
if(s[T])break;
while(true)if(tmp=find(S,inf))ans+=tmp;else break;
}
}
int Test;
int main()
{
scanf("%d",&Test);
for(;Test;--Test)
{
scanf("%d%d%d%d",&n,&m,&u,&v);
S=0;T=n+1;tot=1;ans=sum=0;
for(i=S;i<=T;++i)son[i]=0;
add(S,u,inf);
add(v,T,inf);
for(;m;--m)
{
scanf("%d%d%d",&u,&v,&c);
add(u,v,c*1005+1);
sum+=c;
}
dinic(S,T);
if(ans)printf("%.2lf\n",1.0*(sum-ans/1005)/(ans%1005));
else printf("Inf\n");
}
}
F First Digit
求be的最高位
Solution：log10的精度挂了，于是高精度乱shi
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<algorithm>
using namespace std;
struct huge{
//高精度模版
}a,b,ans;char huge::s[N_huge*10];
char get(long long x){
for(;x>=10;x/=10);return x+48;
}
int T,lim,i;
int main(){
scanf("%d",&T);
lim=(int)T*0.52;
for(i=1;i<=lim;++i)
{
a.read();b.read();
ans=1;
for(;b>0;b/=2){
if(b%2==1)ans*=a;
a=a*a;
}
putchar(get(ans.a[ans.len]));
putchar('\n');
}
for(int i=lim+1;i<=T;++i)puts("9");
}
G Greedy Driver
一个司机要从1到N，他可以卖一次油来偷赚老板的钱，有若干加油点和卖油点，问最大获利
Solution：SPFA求出1到所有卖油点的最大剩油和所有卖油点到N的最小耗油
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,m,a,b,C,u,v,c,i,j,k,ans;
int son[100005],next[100005],ed[100005],cost[100005];
int son2[100005],next2[100005],ed2[100005];
int fuel1[100005],fuel2[100005],val[100005];
int q[1000005],ll,rr;
bool A[100005],B[100005],inq[100005];
int main()
{
while(scanf("%d%d%d",&n,&m,&C)!=EOF)
{
for(i=1;i<=n;++i)son[i]=son2[i]=0,A[i]=B[i]=false;
for(i=1;i<=m;++i)
{
scanf("%d%d%d",&u,&v,&c);
next[i]=son[u];son[u]=i;ed[i]=v;cost[i]=c;
next2[i]=son2[v];son2[v]=i;ed2[i]=u;
}
scanf("%d",&a);
for(;a;--a)
{
scanf("%d",&u);
A[u]=true;
}
scanf("%d",&b);
for(;b;--b)
{
scanf("%d",&u);
scanf("%d",&val[u]);
B[u]=true;
}
for(i=1;i<=n;++i)fuel1[i]=-1,inq[i]=false;
fuel1[1]=C;
q[1]=1;ll=0;rr=1;inq[1]=true;
while(ll!=rr)
{
++ll;if(ll>1000000)ll=1;
u=q[ll];inq[u]=false;
for(i=son[u];i;i=next[i])
if(fuel1[u]-cost[i]>fuel1[ed[i]])
{
fuel1[ed[i]]=fuel1[u]-cost[i];
if(A[ed[i]])fuel1[ed[i]]=C;
if(!inq[ed[i]])
{
++rr;if(rr>1000000)rr=1;
q[rr]=ed[i];
inq[ed[i]]=true;
}
}
}
if(fuel1[n]==-1)
{
printf("-1\n");
continue;
}
for(i=1;i<=n;++i)fuel2[i]=C+1,inq[i]=false;
fuel2[n]=0;
q[1]=n;ll=0;rr=1;inq[n]=true;
while(ll!=rr)
{
++ll;if(ll>1000000)ll=1;
u=q[ll];inq[u]=false;
for(i=son2[u];i;i=next2[i])
if(fuel2[u]+cost[i]<fuel2[ed2[i]])
{
fuel2[ed2[i]]=fuel2[u]+cost[i];
if(A[ed2[i]])fuel2[ed2[i]]=0;
if(!inq[ed2[i]])
{
++rr;if(rr>1000000)rr=1;
q[rr]=ed2[i];
inq[ed2[i]]=true;
}
}
}
ans=0;
for(i=1;i<=n;++i)
if(B[i]&&(fuel1[i]-fuel2[i])*val[i]>ans)
ans=(fuel1[i]-fuel2[i])*val[i];
printf("%d\n",ans);
}
}
H Grouping
给出若干信息，s≥t，把这些数分组，使每个组中，各个数都不能比较大小
Solution：tarjan缩点，求出拓扑序后DP
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,m,u,v,i,j,k,ans,tot;
int st[100001],len,tarjan_index,newdot;
struct Graph_old
{
int son;
int dfn,low,from;
bool inst;
}graph[100001];
struct Graph_new
{
int son,tot,init;
}Graph[100001];
struct Edge_node
{
int next,ed;
}e[1000001],E[1000001];
int tot1,tot2;
void addedge(int u,int v){++tot1;e[tot1].next=graph[u].son;graph[u].son=tot1;e[tot1].ed=v;}
void Addedge(int u,int v){++tot2;E[tot2].next=Graph[u].son;Graph[u].son=tot2;E[tot2].ed=v;}
void tarjan(int now)
{
int i;
graph[now].dfn=graph[now].low=++tarjan_index;
st[++len]=now;
graph[now].inst=true;
for(i=graph[now].son;i;i=e[i].next)
if(!graph[e[i].ed].dfn)
{
tarjan(e[i].ed);
if(graph[e[i].ed].low<graph[now].low)
graph[now].low=graph[e[i].ed].low;
}
else
{
if((graph[e[i].ed].inst)&&(graph[e[i].ed].low<graph[now].low))
graph[now].low=graph[e[i].ed].low;
}
if(graph[now].dfn==graph[now].low)
{
++newdot;
for(;st[len]!=now;)
{
graph[st[len]].inst=false;
graph[st[len]].from=newdot;
++Graph[newdot].tot;
--len;
}
graph[st[len]].inst=false;
graph[st[len]].from=newdot;
++Graph[newdot].tot;
--len;
}
}
void Tarjan()
{
int i,j;
for(i=1;i<=n;++i)
if(!graph[i].dfn)tarjan(i);
for(i=1;i<=n;++i)
for(j=graph[i].son;j;j=e[j].next)
if(graph[i].from!=graph[e[j].ed].from)
{
++Graph[graph[e[j].ed].from].init;
Addedge(graph[i].from,graph[e[j].ed].from);
}
}
int dist[100005];
void Topsort()
{
int i,queue[100001],t1=0,t2=0,now,aim;
for(i=1;i<=newdot;++i)
if(Graph[i].init==0)
queue[++t2]=i;
while(t1<t2)
{
now=queue[++t1];dist[now]+=Graph[now].tot;
if(dist[now]>ans)ans=dist[now];
for(i=Graph[now].son;i;i=E[i].next)
{
aim=E[i].ed;
if(dist[now]>dist[aim])dist[aim]=dist[now];
--Graph[aim].init;
if(Graph[aim].init==0)queue[++t2]=aim;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;++i)dist[i]=0;
for(i=1;i<=n;++i)graph[i].dfn=graph[i].low=graph[i].from=graph[i].son=Graph[i].son=Graph[i].tot=0;
for(;m;--m)
{
scanf("%d%d",&u,&v);
addedge(u,v);
}
tot1=tot2=len=tarjan_index=newdot=0;
Tarjan();
ans=0;
Topsort();
printf("%d\n",ans);
}
}
I Left 4 Dead
J Sister's Noise
2022年8月30日 01:34
The Primary School Certificate Examination tests 2022 are successfully completed in November for all education boards across the country all divisions, and they have going to announce PSC Result 2022 Sylhet Board with full mark sheet under DPE along with Sylhet board for the academic terminal examination tests. PSC Result Sylhet Board Based on the DPE announcement there are 30 lacks of students are participated from all divisions across the country for this Primary Education Course (PEC) from all education boards included the Sylhet board, every year those Grade-5 Terminal annual final exams are conducted under the Directorate of Primary Education (DPE) and this year also conducted same without delay.