标签：ch const int while return CSP 模拟 getchar
欠的太多了，就少说点吧
把数组 \(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);
}
题目看着挺难受，但要求的比较简单，我们只需要判一下环，然后看是否有两个自环相联通，直接 \(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;
}
博弈论，结论是，如果是偶数并且两两相互配对则必胜，否则必败。
点击查看代码
#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");
}
}
标签：ch,
const,
int,
while,
return,
CSP,
模拟,
getchar
From： https://www.cnblogs.com/zhengchenxi/p/18454933