2018.11.3 PION模拟赛
分类:
IT文章
•
2025-01-27 08:07:26
期望：100 实际：100
![]()
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n,s,num;
int a[MAXN];
long long ans;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int cmp(int x,int y){
return x>y;
}
int main(){
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
n=read();s=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n,cmp);
int mid=n/2;
for(int i=1;i<=n;i++)
if(a[i]>=s) num++;
else{
if(num<=mid){
ans+=(s-a[i]);num++;
}
else if(num>mid) break;
}
cout<<ans;
}
100
期望：20~40 实际：0
![]()
/*
思路：感觉可以用卡特兰数搞一下。
应该可以推出递推式。
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p,k;
long long ans;
int vis[10010];
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void dfs(int now,int num1,int num2){
if(num1>n) return ;
if(num1+(2*n-now)+1<n) return ;
if(num2-num1>=k) return ;
if(now==2*n+1){
if(num1==n){
ans+=1;
ans%=p;
}
return ;
}
vis[now]=1;dfs(now+1,num1+1,num2);vis[now]=0;
dfs(now+1,num1,num2+1);
}
int main(){
freopen("term.in","r",stdin);
freopen("term.out","w",stdout);
n=read();k=read();p=read();
if(n<=15){
dfs(1,0,0);
printf("%d
",ans);
}
else if(k==1){
ans=1;
for(int i=2*n;i>=n+2;i--){
int j=2,num=i;
while(j<=n){
if(!vis[j]){
if(num%j==0){
num/=j;
vis[j]=1;
}
}
j++;
}
ans=ans*num;
}
for(int i=2;i<=n;i++)
if(!vis[i]) ans/=i;
cout<<ans%p;
}
}
0
看出是卡特兰数了，但是对于非质数的除法取莫出现了问题
![]()
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,k,p,tot;
int prime[10000],num[100000];
int vis[10010],mn[100010],yes[100010];
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void pre(){
memset(yes,true,sizeof(yes));
yes[1]=false;
for(int i=2;i<=2*n;i++){
if(yes[i]) prime[++tot]=i,mn[i]=tot;
for(int j=1;i*prime[j]<=n;j++){
yes[i*prime[j]]=false;
if(i%prime[j]==0) break;
}
}
}
void insert(int x,int opt){
while(x!=1){
num[mn[x]]+=opt;
x=x/prime[mn[x]];
}
}
int fastpow(long long a,long long b){
long long s=1;
for(;b;b>>=1){
if(b&1) s=a*a%p;
a=a*a%p;
}
return s;
}
int findans(){
long long ans=1;
for(int i=1;i<=tot;i++)
if(num[i])
ans=(1ll*ans*fastpow(prime[i],num[i]))%p;
return ans;
}
int main(){
// freopen("term.in","r",stdin);
//freopen("term.out","w",stdout);
n=read();k=read();p=read();
pre();
for(int i=n+1;i<=2*n;i++) insert(i,1);
for(int i=1;i<=n;i++) insert(i,-1);
long long ans1=findans();
memset(num,0,sizeof(num));
for(int i=n+k+1;i<=2*n;i++) insert(i,1);
for(int i=1;i<=n-k;i++) insert(i,-1);
long long ans2=findans();
cout<<(ans1-ans2+p)%p;
}
100
![]()
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 500010
using namespace std;
map<int,bool>ma[MAXN];
int tim,top,sumcol;
int n,m,s,t,tot,tot1,tot2;
struct nond{ int id,dis; };
int low[MAXN],dfn[MAXN],col[MAXN];
int val[MAXN],val1[MAXN],di[MAXN],dis[MAXN];
int stack[MAXN],vis[MAXN],visstack[MAXN];
int to[MAXN],cap[MAXN],net[MAXN],head[MAXN];
int to1[MAXN],cap1[MAXN],net1[MAXN],head1[MAXN];
int to2[MAXN],cap2[MAXN],net2[MAXN],head2[MAXN];
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void add(int u,int v,int w){
to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot;
}
void add2(int u,int v,int w){
to1[++tot1]=v;cap1[tot1]=w;net1[tot1]=head1[u];head1[u]=tot1;
}
void add3(int u,int v,int w){
to2[++tot2]=v;cap2[tot2]=w;net2[tot2]=head2[u];head2[u]=tot2;
}
void tarjin(int now){
low[now]=dfn[now]=++tim;
stack[++top]=now;
vis[now]=1;visstack[now]=1;
for(int i=head[now];i;i=net[i])
if(visstack[to[i]])
low[now]=min(low[now],dfn[to[i]]);
else if(!vis[to[i]]){
tarjin(to[i]);
low[now]=min(low[now],low[to[i]]);
}
if(dfn[now]==low[now]){
sumcol++;
col[now]=sumcol;
while(stack[top]!=now){
col[stack[top]]=sumcol;
visstack[stack[top]]=0;
top--;
}
visstack[now]=0;
top--;
}
}
void spfa(int S){
queue<int>que;
memset(vis,0,sizeof(vis));
memset(di,0x7f,sizeof(di));
vis[S]=1;di[S]=val1[S];
que.push(S);
while(!que.empty()){
int now=que.front();
que.pop();
vis[now]=0;
for(int i=head1[now];i;i=net1[i])
if(di[to1[i]]>=(di[now]&cap1[i]&val1[to1[i]])){
di[to1[i]]=(di[now]&cap1[i]&val1[to1[i]]);
if(!vis[to1[i]]){
vis[to1[i]]=1;
que.push(to1[i]);
}
}
}
}
void spfa1(int S){
queue<int>que;
memset(vis,0,sizeof(vis));
memset(dis,0x7f,sizeof(di));
vis[S]=1;dis[S]=val1[S];
que.push(S);
while(!que.empty()){
int now=que.front();
que.pop();
vis[now]=0;
for(int i=head2[now];i;i=net2[i])
if(dis[to2[i]]>=(dis[now]&cap2[i]&val1[to2[i]])){
dis[to2[i]]=(dis[now]&cap2[i]&val1[to2[i]]);
if(!vis[to2[i]]){
vis[to2[i]]=1;
que.push(to2[i]);
}
}
}
}
int main(){
freopen("rabbit.in","r",stdin);
freopen("rabbit.out","w",stdout);
n=read();m=read();s=read();t=read();
for(int i=1;i<=n;i++) val[i]=read();
for(int i=1;i<=m;i++){
int u=read();
int v=read();
int w=read();
add(u,v,w);
}
for(int i=1;i<=n;i++)
if(!vis[i]) tarjin(i);
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=net[j])
if(col[i]!=col[to[j]])
if(ma[col[i]].find(col[to[j]])==ma[col[i]].end()){
ma[col[i]][col[to[j]]]=1;
add2(col[i],col[to[j]],cap[j]);
add3(col[to[j]],col[i],cap[j]);
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
if(!vis[col[i]]) val1[col[i]]=val[i],vis[col[i]]=1;
else val1[col[i]]=(val1[col[i]]&val[i]);
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=net[j])
if(col[i]==col[to[j]])
val1[col[i]]=(val1[col[i]]&cap[j]);
spfa(col[s]);
spfa1(col[t]);
if(di[col[t]]==0x7f7f7f7f){ puts("-1");return 0; }
else{ printf("%d
",min(di[col[t]],dis[col[s]]));return 0; }
}
