©2020-2024 ioDraw All rights reserved
<>总结
<>提高组
<>T1 丹钓战
考场时想的就是从头到尾模拟一遍，找到每一个二元组最前一个不会被弹出的二元组是哪个。然后将询问离线，按 r i r_i ri
从小到大排序。再从头来一遍，将每个点的前驱存入数状数组，每到一个 r i r_i ri就用数状数组查询在 l i l_i li和 r i r_i ri
之间的前驱小于 l i l_i li的二元组个数，即为此查询的答案。
预估: 100
实际: 100
AC代码如下
#include<bits/stdc++.h> using namespace std; int n,q,top=0,now=1,t,sp=0,a[
500005],b[500005],f[500005],h[500005],ans[500005],tr[500005]; struct node{ int l
,r,id; }p[500005]; bool cmp(node ax,node bx){ return ax.r<bx.r; } int lb(int i){
return i&(-i); } void pt(int i){ if(!i){ ++sp;return; } for(;i<=n;i+=lb(i)) ++tr
[i]; } int gt(int i){ int re=sp; for(;i;i-=lb(i)) re+=tr[i]; return re; } int
main() { // freopen("stack.in","r",stdin); // freopen("stack.out","w",stdout);
scanf("%d%d",&n,&q); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=
n;i++){ scanf("%d",&b[i]); } for(int i=1;i<=n;i++){ while(top>0&&(a[h[top]]==a[i
]||a[h[top]]!=a[i]&&b[h[top]]<=b[i])) --top; f[i]=h[top];h[++top]=i; } for(int i
=1;i<=q;i++){ scanf("%d%d",&p[i].l,&p[i].r); p[i].id=i; } sort(p+1,p+q+1,cmp);
for(int i=1;i<=n;i++){ pt(f[i]); while(i==p[now].r&&now<=q){ t=gt(p[now].l-1); t
=p[now].r-t; t=p[now].r-p[now].l+1-t; ans[p[now].id]=t; ++now; } } for(int i=1;i
<=q;i++){ printf("%d\n",ans[i]); } // fclose(stdin); // fclose(stdout); //
return 0; }
<>T2 讨论
题目就是给出每个人会的题，求两个人，满足他们有都会的题，且有自己会对方不会的题。
输入后按每个人会做的题数从大到小排序，在从大到小枚举每一个人会的每一道题。用一个存每一道题目前枚举到的最后一个会做的人，在枚举每一个人的时候更新桶。设枚举到
i ii。在更新桶之前，看一下此人每一道会的题上一个是不是同一个人。设前人为 k k k。是则 i ⊆ k i\subseteq k i⊆k
，不能讨论；不是则找排名更后的那个人，假设就是 k k k，因为 i i i有 k k k不会的题，而 k k k排名在 i i i前，会的题更多，自然有 i
ii不会的题，所以 i i i和 k k k可以讨论。
但是，考场上没有AC，有一种情况没有考虑。若枚举 i i i时没有上一个，即上一个为空，这道题目前只有 i i i会，则之后枚举到的任意一个 k k k
都可以与 i i i讨论
预估: 100
实际: 60
没AC原因: 数组开小(10 pts)+少考虑一种情况(30 pts)
AC代码如下
#include<bits/stdc++.h> using namespace std; int t,n,x,tot,tp,now,k[2000005],p[
2000005],d[2000005],l[2000005],r[2000005],y[2000005],v[2000005]; bool f; void
add(int xx,int yy){ l[++tot]=r[xx];d[tot]=yy;r[xx]=tot; } bool cmp(int ax,int bx
){ return k[ax]>k[bx]; } int main() { // freopen("discuss.in","r",stdin); //
freopen("discuss.out","w",stdout); scanf("%d",&t); while(t--){ scanf("%d",&n);
tot=0;f=0; for(int i=1;i<=n;i++){ scanf("%d",&k[i]); for(int j=1;j<=k[i];j++){
scanf("%d",&x); add(i,x); } p[i]=i; } sort(p+1,p+n+1,cmp); for(int i=1;i<=n;i++)
y[p[i]]=i; for(int i=1;i<=n;i++){ int u=p[i],vs=0;tp=0; for(int j=r[u];j;j=l[j]
){ if(v[d[j]]){ if(tp&&tp!=v[d[j]]){ if(y[tp]<y[v[d[j]]]) tp=v[d[j]]; f=1;now=i;
break; } else if(!tp){ tp=v[d[j]]; if(vs){ f=1;now=i; } } } else{ if(!v[d[j]]&&
tp){ f=1;now=i; } if(!v[d[j]]) vs=1; } v[d[j]]=u; } if(f) break; } if(!f) printf
("NO\n"); else{ printf("YES\n%d %d\n",p[now],tp); } for(int i=1;i<=n;i++){ r[i]=
v[i]=y[i]=p[i]=k[i]=0; } } // fclose(stdin); // fclose(stdout); // return 0; }
<>T3 如何正确的排序
考场有点思路，但没打出来，只打了暴力。暴力代码就不放了
暴力打的是 k = 2 k=2 k=2和 n ≤ 3000 n\leq3000 n≤3000的情况，但 k = 2 k=2 k=2
的情况有一个细节打挂了，又丢10 pts
预估: 20
实际: 10
没达到预估成绩原因: 细节打挂
<>提高组总结
整体发挥的还行，但细节失误过多
预估: 100+100+20=220
应得: 100+100+20=220
实际: 100+60+10=170
<>普及组
<>T1 王国比赛
比较简单，模拟一遍即可
#include<iostream> #include<cstdio> using namespace std; int n,m,ans,a[1005][
1005],v[1005],b[1005]; int main() { // freopen("kingdom.in","r",stdin); //
freopen("kingdom.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){ scanf("%d",&a[i][j]); v[j]+=a[i][j]; } } for(int i=1;i<=n
;i++){ scanf("%d",&b[i]); } for(int i=1;i<=n;i++){ if(v[i]>m-v[i]&&b[i]) ++ans;
if(v[i]<m-v[i]&&!b[i]) ++ans; } printf("%d",ans); // fclose(stdin); //
fclose(stdout); // return 0; }
<>T2 数学游戏
题目即给出 x x x和 z z z的值，问是否有能满足 z = x × y × g c d ( x , y ) z=x\times y\times
gcd(x,y)z=x×y×gcd(x,y)的 y y y，有的话输出 y y y的值
这是一道思维题，设 d = g c d ( x , y ) , d x ′ = x , d y ′ = y d=gcd(x,y),dx'=x,dy'=y d=
gcd(x,y),dx′=x,dy′=y，易得 x ′ x' x′与 y ′ y' y′互质，则 z = x × y × g c d ( x , y ) =
d x ′ × d y ′ × d = d 3 x ′ y ′ z=x\times y\times gcd(x,y)=dx'\times dy'\times
d=d^3x'y'z=x×y×gcd(x,y)=dx′×dy′×d=d3x′y′，所以 z x = d 2 y ′ \frac{z}{x}=d^2y' xz=
d2y′。又因为 x 2 = d 2 x ′ 2 x^2=d^2x'^2 x2=d2x′2，因为 x ′ x' x′与 y ′ y' y′互质，所以 x ′
2 x'^2x′2与 y ′ y' y′互质，所以 g c d ( x 2 , z x ) = d 2 gcd(x^2,\frac{z}{x})=d^2 gcd
(x2,xz)=d2，得出 d 2 d^2 d2，即可得出 d d d
#include<iostream> #include<cstdio> #include<cmath> using namespace std; long
long x,y,z,z1,g,d; int t,n,p[100005]; long long gcd(long long i,long long j){
while(j>0){ i%=j;swap(i,j); } return i; } int main() { //
freopen("math.in","r",stdin); // freopen("math.out","w",stdout); scanf("%d",&t);
while(t--){ scanf("%lld%lld",&x,&z); if(z%x!=0){ printf("-1\n"); continue; } z/=
x; g=gcd(x*x,z); d=sqrt(g); if(d*d!=g){ printf("-1\n"); continue; } y=z/d; if(
gcd(x,y)!=d){ printf("-1\n"); continue; } printf("%lld\n",y); } //
fclose(stdin); // fclose(stdout); // return 0; }
<>T3 字符串
考场没做出来，打的是暴力
<>普及组总结
普及组发挥一般，只有205分，下次还要继续努力