\(T1:\)median
思路:
根据题目要求,我们不难发现题目要求的就是每个合法的数(即能够成为中位数)作为中位数的情况数×该数,最后对所有情况进行求和。显然,我们要枚举每一个数作为中位数,那么在另外四组里一定有两个比它小的,两个比它大的。然后就哪两个大于哪两个小于进行分讨,分别求出每组大于它和小于它的数的个数。最后,根据乘法原理把四个组的答案乘起来就好了。
注意,题目并没有说每组的数字和别组的数字不重复,所以我们要进行大量的容斥。为了避免大量的容斥,我们可以将\(A\)组的数乘以5加1,\(B\)组的数乘以5加2,\(C\)组的数乘以5加3,以此类推。这样我们就可以保证不同的组之间不会出现相同的数了。为什么呢?我们不妨反证一下。假设有\(A\),\(B\)两组里处理之后有两个相同的数分别为\(x\),\(y\),那么我们可以得出式子\(5x+1=5y+2\),整理得\(5(x-y)=1\),即\(x-y=\frac{1}{5}\),又因为\(x\),\(y\)一定为正整数,所以无解。其他的同理。一定得是5吗?不一定,只要大于五就行。可以证明。当乘以4时,\(A\),\(E\)两组中\(4x+1=4y+5\),解得\(x-y=1\),此时有解,所以小于5不行。
代码:
$code$
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+5,mod=998244353;
int n,ans,a[5][N],b[5][N],l[N];
signed main(){
// freopen("median.in","r",stdin);
// freopen("median.out","w",stdout);cin>>n;for(int i=0;i<5;i++) for(int j=1;j<=n;j++) cin>>a[i][j];for(int i=0;i<5;i++) sort(a[i]+1,a[i]+1+n);for(int i=0;i<5;i++) for(int j=1;j<=n;j++) b[i][j]=(a[i][j]*5)+i;for(int i=0;i<5;i++){l[0]=l[1]=l[2]=l[3]=l[4]=0;int i1=(i+1)%5,i2=(i+2)%5,i3=(i+3)%5,i4=(i+4)%5;for(int r=1;r<=n;r++){while(l[i1]+1<=n&&b[i1][l[i1]+1]<=b[i][r]) ++l[i1];//1组 while(l[i2]+1<=n&&b[i2][l[i2]+1]<=b[i][r]) ++l[i2];//2组 while(l[i3]+1<=n&&b[i3][l[i3]+1]<=b[i][r]) ++l[i3];//3组 while(l[i4]+1<=n&&b[i4][l[i4]+1]<=b[i][r]) ++l[i4];//4组 ans=(ans+(l[i1]*l[i2]%mod*(n-l[i3])%mod*(n-l[i4])%mod+//1 2组大于,3 4组小于 l[i1]*l[i3]%mod*(n-l[i2])%mod*(n-l[i4])%mod+//1 3组大于,2 4组小于 l[i1]*l[i4]%mod*(n-l[i2])%mod*(n-l[i3])%mod+//1 4组大于,2 3组小于 l[i2]*l[i3]%mod*(n-l[i1])%mod*(n-l[i4])%mod+//2 3组大于,1 4组小于 l[i2]*l[i4]%mod*(n-l[i3])%mod*(n-l[i1])%mod+//2 4组大于,1 3组小于 l[i3]*l[i4]%mod*(n-l[i1])%mod*(n-l[i2])%mod //3 4组大于,1 2组小于 )%mod*a[i][r]%mod)%mod;//分讨 }}cout<<ans<<'\n';return 0;
}/*
自造数据:3
1 2 7
3 5 8
2 4 6
5 7 9
2 3 62
1 2
3 5
2 4
5 7
7 9
*/
\(T2:\) travel
思路:
阅读题面,我们发现题目要求的就是输入的图是否存在\(x,y\),使得\(f(x,y,k)\)没有渐近线。那么我们来考虑既然\(f\)没有渐近线,那要么当\(k\)趋向正无穷的时候\(f\)也趋向正无穷;要么\(f\)在某两个值之间震荡(可类比三角函数)。那么我们考虑什么情况下\(f\)是上述的合法函数。
-
一个点有两个自环。设这个点为\(x\),那么\(f(x,x,k)\)是一个合法的函数,通过调换自环的顺序,当\(k\)趋向于正无穷的时候,\(f\)也趋向于正无穷。
-
有两个自环。设这两个点为\(x,y\),那么\(f(x,y,k)\)是一个合法的函数,通过调换自环的顺序,当\(k\)趋向于正无穷的时候,\(f\)也趋向于正无穷。
-
存在一个二元环\(x,y\),那么\(f(x,y,k)\)是一个合法的函数,\(f\)的值在\(0,1\)之间震荡
代码:
$code$
#include<iostream>
using namespace std;
const int N=5e5+5;
int m,n,u,v,loop[N],vis[N],in[N],head[N],cnt;
struct node{int to,nxt;}e[N<<1];
inline void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;
}//建图
inline bool dfs(int x){in[x]=vis[x]=1;for(int i=head[x];i;i=e[i].nxt){int y=e[i].to;if(loop[x]&&loop[y]) return 1;//有两个自环 if(in[x]&&in[y]) return 1;//x,y在同一个环里 if(vis[y]) continue;//已经搜过了 if(dfs(y)) return 1;//继续搜 }in[x]=0;//当前环遍历完成,清空标记 return 0;
}
int main(){freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=m;i++){cin>>u>>v;if(u==v){if(loop[u]){//一个点有两个自环 cout<<"Yes"<<'\n';return 0;}loop[u]=1;//标记 }else add(u,v);}for(int i=1;i<=n;i++){if(!vis[i]){if(dfs(i)){cout<<"Yes"<<'\n';return 0;}}}cout<<"No"<<'\n';return 0;
}//使函数不收敛的图是有趣的
\(T3:\) game
思路:
结论: 若\(a_i\)能两两相同配对则后手胜,否则先手必胜。
证明: 设\(S\)为满足上述条件的集合,我们来证明:①\(S\)中的元素经过一步操作后必不在\(S\)中,②\(S\)以外的元素能经过一步操作走到\(S\)内。
-
①选取任意一对\((x,x)\),分为两种情况。要么直接拿走\(a\)个石子,此时一定不属于\(S\)。要么用\(k\)个石子填补其他的石子堆,将其中一个原本较矮的石子堆填补为\(x\)个石子,这种情况可以转化为选了一对\((<x,<x)\)的并对其进行情况一的操作。
-
②将所有元素排好序后,选择最大的不能配对的,用其将其他石子堆填补为两两配对的样子,其所需的石子数为\(\sum a_i-a_{i-1}\),是差分的和,不会超过最大值,所以一定存在一种分配方案使得该序列进入\(S\)。
由上述证明可得,\(S\)内外元素的转化只需要一步。因此,若先手面对的是\(S\)内的元素,那么ta用一步将其转化为\(S\)内的元素,然后后手又用一步将其转化为\(S\)外的元素。以此类推,\(S\)内的元素需要\(2n\)步结束游戏,此时显然后手赢。反之,则先手必胜。
代码:
$code$
#include<iostream>
#include<map>
using namespace std;
const int N=2e5+5;
int T,n,a[N];map<int,int> mp;bool f;
int main(){
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);ios::sync_with_stdio(false);cin>>T;while(T--){cin>>n;mp.clear();f=0;for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;for(int i=1;i<=n;i++){if(mp[a[i]]%2!=0){f=1;break;}}//两两配对 if(!f){cout<<"No"<<'\n';continue;}//能配上 cout<<"Yes"<<'\n';//配不上 }return 0;
}