欠的太多了,就少说点吧
把数组 \(a,b,c,d,e\) 存到一起,标记类型,然后排序,枚举每个数为中位数,算贡献即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;#define int long long
const int N=1e5+107;
const int mod=998244353;
int n;struct lmy
{int val,op;int s[6];int h[6];
}a[N*5];bool comp(lmy a,lmy b)
{return a.val<b.val;
}int read()
{int f=1,s=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return f*s;
}int get(int i)
{int x=a[i].op;
// cout<<x<<endl;int s1=a[i].s[1],s2=a[i].s[2],s3=a[i].s[3],s4=a[i].s[4],s5=a[i].s[5];int h1=a[i].h[1],h2=a[i].h[2],h3=a[i].h[3],h4=a[i].h[4],h5=a[i].h[5];int ans1=(x!=1?0:s2*s3%mod*h4%mod*h5%mod+s2*s4%mod*h3%mod*h5%mod+s2*s5%mod*h3%mod*h4%mod+s3*s4%mod*h2%mod*h5%mod+s3*s5%mod*h2%mod*h4%mod+s4*s5%mod*h2%mod*h3%mod);int ans2=(x!=2?0:s1*s3%mod*h4%mod*h5%mod+s1*s4%mod*h3%mod*h5%mod+s1*s5%mod*h3%mod*h4%mod+s3*s4%mod*h1%mod*h5%mod+s3*s5%mod*h1%mod*h4%mod+s4*s5%mod*h1%mod*h3%mod);int ans3=(x!=3?0:s2*s1%mod*h4%mod*h5%mod+s2*s4%mod*h1%mod*h5%mod+s2*s5%mod*h1%mod*h4%mod+s1*s4%mod*h2%mod*h5%mod+s1*s5%mod*h2%mod*h4%mod+s4*s5%mod*h2%mod*h1%mod);
// if(a[3].op==x) cout<<s1<<" "<<s2<<" "<<s3<<" "<<s4<<" "<<s5<<endl; int ans4=(x!=4?0:s2*s3%mod*h1%mod*h5%mod+s2*s1%mod*h3%mod*h5%mod+s2*s5%mod*h3%mod*h1%mod+s3*s1%mod*h2%mod*h5%mod+s3*s5%mod*h2%mod*h1%mod+s1*s5%mod*h2%mod*h3%mod);int ans5=(x!=5?0:s2*s3%mod*h4%mod*h1%mod+s2*s4%mod*h3%mod*h1%mod+s2*s1%mod*h3%mod*h4%mod+s3*s4%mod*h2%mod*h1%mod+s3*s1%mod*h2%mod*h4%mod+s4*s1%mod*h2%mod*h3%mod);return ans1+ans2+ans3+ans4+ans5;
}signed main()
{freopen("median.in","r",stdin);freopen("median.out","w",stdout);n=read();for(int i=1;i<=5;i++){for(int j=1;j<=n;j++){a[(i-1)*n+j]={read(),i};}}sort(a+1,a+1+n*5,comp);for(int i=1;i<=n*5;i++){for(int j=1;j<=5;j++){a[i].s[j]=a[i-1].s[j]+(a[i].op==j);}}for(int i=n*5;i>=1;i--){for(int j=1;j<=5;j++){a[i].h[j]=a[i+1].h[j]+(a[i].op==j);}}// for(int i=1;i<=n*5;i++)
// {
// cout<<a[i].op<<" ";
// }cout<<endl;
// for(int i=1;i<=n*5;i++)
// {
// cout<<a[i].val<<" ";
// }cout<<endl;// for(int i=1;i<=n*5;i++)
// {
// cout<<"------------------\n";
// cout<<i<<" "<<a[i].val<<" "<<a[i].op<<endl;
// for(int j=1;j<=5;j++)
// {
// cout<<a[i].s[j]<<" ";
// }cout<<endl;
// for(int j=1;j<=5;j++)
// {
// cout<<a[i].h[j]<<" ";
// }cout<<endl;
// cout<<a[i].val*get(i)<<endl;
// }int ans=0;for(int i=1;i<=n*5;i++){ans=(ans+a[i].val*get(i)%mod)%mod;}printf("%lld",ans);
}
T2.travel
题目看着挺难受,但要求的比较简单,我们只需要判一下环,然后看是否有两个自环相联通,直接 \(dfs\) 一遍即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;const int N=1e6+107;
int n,m;
int du[N];int read()
{int f=1,s=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return f*s;
}int h[N],to[N],nxt[N],tot;
void add(int x,int y)
{to[++tot]=y;nxt[tot]=h[x];h[x]=tot;
}int dep[N],vis[N],flag[N];
int dfs(int u,int fa)
{dep[u]=1;int ans=vis[u];for(int i=h[u];i;i=nxt[i]){int v=to[i];if(dep[v]) return 2;ans+=dfs(v,u);}dep[u]=0;return ans;
}int main()
{freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);n=read(),m=read();for(int i=1;i<=m;i++){int u=read(),v=read();if(u==v) vis[u]++;else add(u,v);if(vis[u]>=2) return printf("Yes\n"),0;}for(int i=1;i<=n;i++){if(dfs(i,i)>=2) return printf("Yes\n"),0;}printf("No\n");return 0;
}
T3.game
博弈论,结论是,如果是偶数并且两两相互配对则必胜,否则必败。
点击查看代码
#include<bits/stdc++.h>
using namespace std;const int N=5e5+107;
int n,a[N];int read()
{int f=1,s=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return f*s;
}int main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);int T=read();while(T--){int flag=0;n=read();for(int i=1;i<=n;i++) a[i]=read();sort(a+1,a+1+n);for(int i=1;i<=n;i+=2){if(a[i]!=a[i+1]) {flag=1;break;}}if(!(n&1)&&!flag) printf("No\n");else printf("Yes\n");}}