1001 Alisha’s Party
比赛的时候学长stl吃T。手写堆过。
赛后我贴了那两份代码都过。相差.2s。
于是用stl写水果。
# include <iostream>
# include <cstdio>
# include <algorithm>
# include <queue>
using namespace std;
# define maxk
int ans[maxk]; struct node
{
char name[];
int id,val;
friend bool operator < (node x,node y)
{
if(x.val!=y.val) return x.val<y.val;
return x.id>y.id;
}
} p[maxk];
priority_queue<node> pq; struct open
{
int t,p;
} T[maxk]; bool cmp(open x,open y)
{
return x.t<y.t;
} int main(void)
{
int kase; cin>>kase;
while(kase--)
{
int k,m,q,pos=,cnt=,Q;
scanf("%d%d%d",&k,&m,&q);
for(int i=;i<=k;i++)
{
scanf("%s%d",p[i].name,&p[i].val);
p[i].id=i;
}
for(int i=;i<m;i++) scanf("%d%d",&T[i].t,&T[i].p);
sort(T,T+m,cmp);
while(!pq.empty()) pq.pop();
for(int i=;i<m;i++)
{
while(pos<=k&&pos<=T[i].t) pq.push(p[pos++]);
while(!pq.empty()&&T[i].p--)
{
ans[++cnt]=pq.top().id;
pq.pop();
}
}
while(pos<=k) pq.push(p[pos++]);
while(!pq.empty())
{
ans[++cnt]=pq.top().id;
pq.pop();
}
for(int i=;i<q;i++)
{
scanf("%d",&Q);
printf("%s ",p[ans[Q]].name);
}
scanf("%d",&Q);
printf("%s\n",p[ans[Q]].name);
}
return ;
}
Aguin
1002 Ponds
赛时题意错理解成对所有奇数联通子集权值求和……
先dfs或kahn删点。
再遍历一遍所有奇数联通即可。
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
typedef long long LL;
const int maxp=,maxm=;
int cnt,headlist[maxp],v[maxp],deg[maxp];
bool vis[maxp];
LL tmp; struct node
{
int to,pre;
} edge[*maxm]; void add(int from,int to)
{
cnt++;
edge[cnt].pre=headlist[from];
edge[cnt].to=to;
headlist[from]=cnt;
return;
} void dfs1(int pos)
{
deg[pos]=; vis[pos]=;
for(int i=headlist[pos];i;i=edge[i].pre)
{
int to=edge[i].to;
if(deg[to]) deg[to]--;
if(deg[to]==) dfs1(to);
}
return;
} int dfs2(int pos)
{
int ret=;
vis[pos]=;
tmp+=v[pos];
for(int i=headlist[pos];i;i=edge[i].pre)
{
int to=edge[i].to;
if(vis[to]) continue;
ret+=dfs2(to);
}
return ret;
} int main(void)
{
int T; cin>>T;
while(T--)
{
cnt=;
memset(headlist,,sizeof(headlist));
memset(deg,,sizeof(deg));
memset(vis,,sizeof(vis));
int p,m; scanf("%d%d",&p,&m);
for(int i=;i<=p;i++) scanf("%d",v+i);
for(int i=;i<m;i++)
{
int a,b; scanf("%d%d",&a,&b);
add(a,b); add(b,a);
deg[a]++; deg[b]++;
}
for(int i=;i<=p;i++) if(deg[i]==) dfs1(i);
LL ans=;
for(int i=;i<=p;i++) if(!vis[i]&°[i])
{
tmp=;
if(dfs2(i)%) ans+=tmp;
}
printf("%I64d\n",ans);
}
return ;
}
Aguin
1003 Aggregated Counting
1004 Clock Adjusting
1005 Travel
赛场题意理解错。哭。
询问排序。并查集按秩合并。对答案的贡献是2*r[u]*r[v]。
# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
int Ans[],pa[],r[]; int Find(int x)
{
return pa[x]==x?x:pa[x]=Find(pa[x]);
} void Union(int x,int y)
{
x=Find(x),y=Find(y);
if(y<x) swap(x,y);
pa[y]=x; r[x]+=r[y];
return;
} struct node
{
int from,to,val;
friend bool operator < (node x,node y)
{
return x.val<y.val;
}
} edge[]; struct Query
{
int no,x;
friend bool operator < (Query a,Query b)
{
return a.x<b.x;
}
}query[]; int main(void)
{
int T; cin>>T;
while(T--)
{
int n,m,q; scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n;i++){pa[i]=i;r[i]=;}
for(int i=;i<m;i++)
scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].val);
sort(edge,edge+m);
for(int i=;i<q;i++)
{
query[i].no=i;
scanf("%d",&query[i].x);
}
sort(query,query+q);
int pos=,ans=;
for(int i=;i<q;i++)
{
while(pos<m&&edge[pos].val<=query[i].x)
{
int u=Find(edge[pos].from),v=Find(edge[pos].to);
pos++;
if(u==v) continue;
ans+=*r[v]*r[u];
Union(u,v);
}
Ans[query[i].no]=ans;
}
for(int i=;i<q;i++) printf("%d\n",Ans[i]);
}
return ;
}
Aguin
1006 Favorite Donut
讨论这个题目经历了几个阶段。
比赛时只知道用最大表示法。
然而由于最大表示法在有多解时返回index最小的。逆时针的处理方法没想好。场上T了。
赛后想到逆时针多解时必成循环。可以用KMP求循环节。两者都是O(n)。
后来经过学长提醒。最大表示法如果处理循环串是k增到m后跳出。
于是可以直接在最大表示法里处理掉循环节。时间上常数优化(并无)。
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
using namespace std;
char s[];
int m; int getMax(int p)
{
int i=,j=,k=;
while(i<m&&j<m&&k<m)
{
int t=s[(i+k)%m]-s[(j+k)%m];
if(!t) k++;
else
{
if(t<) i=max(i+k+,j+);
else j=max(j+k+,i+);
k=;
}
}
if(p&&k==m) return m--(m--min(i,j))%abs(i-j);
return min(i,j);
} int main(void)
{
int T; cin>>T;
while(T--)
{
scanf("%d%s",&m,s);
int op=,a=getMax(),b;
reverse(s,s+m);
b=getMax();
for(int i=;i<m;i++)
{
if(s[(*m--a-i)%m]>s[(b+i)%m]) {op=; break;}
if(s[(*m--a-i)%m]<s[(b+i)%m]) {op=; break;}
}
if(op==) printf("%d 0\n",a+);
else if(op==) printf("%d 1\n",m-b);
else if(a+<=m-b) printf("%d 0\n",a+);
else printf("%d 1\n",m-b);
}
return ;
}
Aguin
1007 The Water Problem
水题。ST/线段树/暴力。
# include <iostream>
# include <cstdio>
# include <cmath>
# include <algorithm>
using namespace std;
# define maxn +
int num[maxn],MAX[maxn][]; int main(void)
{
int T; cin>>T;
while(T--)
{
int N,Q; scanf("%d",&N);
for(int i=;i<=N;i++)
{
scanf("%d",num+i);
MAX[i][]=num[i];
}
for(int j=;j<;j++)
for(int i=;i<=N;i++)
if(i+(<<j)-<=N)
MAX[i][j]=max(MAX[i][j-],MAX[i+(<<j-)][j-]);
scanf("%d",&Q);
for(int i=;i<Q;i++)
{
int m,n; scanf("%d%d",&m,&n);
int k=(log(double(n-m+))/log());
int ans=max(MAX[m][k],MAX[n-(<<k)+][k]);
printf("%d\n",ans);
}
}
return ;
}
Aguin
1008 Elven Postman
1009 Food Problem
1010 Unknown Treasure
1011 Good Numbers
1012 Marisa’s Cake
1013 Robot Dog