/*考虑贪心 把原序列排序后，对于原中位数往后所有比要更改到的值小的都改成它正确性显然。 */ #include#include #include #define N 100007#define ll long longusing namespace std;ll n,m,ans,cnt;ll a[N],sum[N];inline ll read(){ ll x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){ if(c=='0')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int main(){ freopen("median.in","r",stdin); freopen("median.out","w",stdout); n=read();m=read(); if(m==0) {printf("0\n");return 0;} for(int i=1;i<=n;i++) a[i]=read(); int mid=n/2+1; sort(a+1,a+n+1); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; int num=lower_bound(a+1,a+n+1,m)-a; if(num==n+1) ans=mid*m-(sum[n]-sum[mid-1]); else if(num==mid) ans=max(a[mid],m)-min(a[mid],m); else ans=(num-mid)*m-(sum[num-1]-sum[mid-1]); cout< <
/*水水的dp 然而菜死了没想出正解QAQ */ #include#include #include #include
/*K=1显然是Catalan数考虑Catalan数的证明过程若数列不合法，则一定存在一个位置x，在这之前有m个+1，m + k个-1我们把之后的1变为-1，-1变为1则该序列含有N + K个-1， N个1方案数为C(2n, n + k)用总的减去即可*/#include#include #define LL intconst int MAXN = 2 * 1e6 + 10;inline int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){ if(c=='0')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int N, mod, prime[MAXN], vis[MAXN], tot, mn[MAXN], num[MAXN], K;void GetPhi(int N){ vis[1] = 1; for(int i = 2; i <= N; i++) { if(!vis[i]) prime[++tot] = i, mn[i] = tot; for(int j = 1; j <= tot && (i * prime[j] <= N); j++) { vis[i * prime[j]] = 1; mn[i * prime[j]] = j; if(!(i % prime[j])) break; } }}void insert(int x, int opt){ while(x != 1) num[mn[x]] += opt, x = x / prime[mn[x]];}int fastpow(int a, int p){ int base = 1; while(p) { if(p & 1) base = (1ll * base * a) % mod; a = (1ll * a * a) % mod; p >>= 1; } return base;}int FindAns(){ LL ans = 1; for(int i = 1; i <= tot; i++) if(num[i]) ans = (1ll * ans * fastpow(prime[i], num[i])) % mod; return ans;}main(){ N = read();K = read();mod = read(); GetPhi(2 * N); for(int i = N + 1; i <= 2 * N; i++) insert(i, 1); for(int i = 1; i <= N; i++) insert(i, -1); LL 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); LL ans2 = FindAns(); printf("%lld", (ans1 - ans2 + mod) % mod); return 0;}
#include#include #include #include #define N 200007#define M 500007#define inf 0x3f3f3f3fusing namespace std;int n,m,ans,cnt,top,num,S,T;int vis[N],val[N],head[N],val_[N],siz[N];int dfn[N],low[N],sta[N],scc[N],to[N];bool in_st[N];int dis[20][20],d[N];int Head[N];struct edge{ int u,v,nxt,w;}e[M],E[M];struct node{ int sum,x;};inline int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){ if(c=='0')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}inline void add(int u,int v,int w){ e[++cnt].v=v;e[cnt].nxt=head[u];e[cnt].w=w;head[u]=cnt;}inline void Add(int u,int v,int w){ E[++cnt].v=v;E[cnt].nxt=Head[u];E[cnt].w=w;Head[u]=cnt;}void Tarjan(int u){ low[u]=dfn[u]=++cnt;sta[++top]=u;in_st[u]=1; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]); else if(in_st[v]) low[u]=min(low[u],dfn[v]); } int lol=0; if(low[u]==dfn[u]) { num++; while(u!=sta[top]) { lol++; if(sta[top]==S) to[num]=1; if(sta[top]==T) to[num]=2; in_st[sta[top]]=0;scc[sta[top]]=num;top--; } in_st[sta[top]]=0;scc[sta[top]]=num;top--; siz[num]=++lol; }}void bfs(){ queue q;node u; while(!q.empty()) q.pop(); u.x=scc[S];u.sum=val_[scc[S]];vis[scc[S]]=1; q.push(u); while(!q.empty()) { u=q.front();q.pop(); if(u.x==scc[T]) ans=min(ans,u.sum); for(int i=Head[u.x];i;i=E[i].nxt) { int v=E[i].v;node tmp; tmp.sum=u.sum & E[i].w & val_[v];tmp.x=v; q.push(tmp); } }}int main(){ freopen("rabbit.in","r",stdin); freopen("rabbit.out","w",stdout); int x,y,z;memset(dis,127/3,sizeof dis); 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++) { x=read();y=read();z=read(); add(x,y,z); }cnt=0;ans=inf; for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i); for(int i=1;i<=num;i++) for(int j=1;j<=n;j++) { if(scc[j]==i) { if(siz[j]==1) val_[i]=val[j]; else { for(int x=head[j];x;x=e[x].nxt) if(scc[e[x].v]==num) val_[scc[j]]&=val[j]&val[e[x].v]&e[j].w; } } } cnt=0; for(int i=1;i<=n;i++) { for(int j=head[i];j;j=e[j].nxt) { if(scc[i]!=scc[e[j].v]) Add(scc[i],scc[e[j].v],e[j].w); } } bfs(); printf("%d\n",ans); return 0; return 0;}
std可能有锅？
#include#include #include #include #include #include #include #include #include