期望：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=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';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=;i<=n;i++) a[i]=read();
sort(a+,a++n,cmp);
int mid=n/;
for(int i=;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[];
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void dfs(int now,int num1,int num2){
if(num1>n) return ;
if(num1+(*n-now)+<n) return ;
if(num2-num1>=k) return ;
if(now==*n+){
if(num1==n){
ans+=;
ans%=p;
}
return ;
}
vis[now]=;dfs(now+,num1+,num2);vis[now]=;
dfs(now+,num1,num2+);
}
int main(){
freopen("term.in","r",stdin);
freopen("term.out","w",stdout);
n=read();k=read();p=read();
if(n<=){
dfs(,,);
printf("%d\n",ans);
}
else if(k==){
ans=;
for(int i=*n;i>=n+;i--){
int j=,num=i;
while(j<=n){
if(!vis[j]){
if(num%j==){
num/=j;
vis[j]=;
}
}
j++;
}
ans=ans*num;
}
for(int i=;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[],num[];
int vis[],mn[],yes[];
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void pre(){
memset(yes,true,sizeof(yes));
yes[]=false;
for(int i=;i<=*n;i++){
if(yes[i]) prime[++tot]=i,mn[i]=tot;
for(int j=;i*prime[j]<=n;j++){
yes[i*prime[j]]=false;
if(i%prime[j]==) break;
}
}
}
void insert(int x,int opt){
while(x!=){
num[mn[x]]+=opt;
x=x/prime[mn[x]];
}
}
int fastpow(long long a,long long b){
long long s=;
for(;b;b>>=){
if(b&) s=a*a%p;
a=a*a%p;
}
return s;
}
int findans(){
long long ans=;
for(int i=;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+;i<=*n;i++) insert(i,);
for(int i=;i<=n;i++) insert(i,-);
long long ans1=findans();
memset(num,,sizeof(num));
for(int i=n+k+;i<=*n;i++) insert(i,);
for(int i=;i<=n-k;i++) insert(i,-);
long long ans2=findans();
cout<<(ans1-ans2+p)%p;
}
100
发现正反跑spfa有70分。
#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=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';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]=;visstack[now]=;
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]]=;
top--;
}
visstack[now]=;
top--;
}
} void spfa(int S){
queue<int>que;
memset(vis,,sizeof(vis));
memset(di,0x7f,sizeof(di));
vis[S]=;di[S]=val1[S];
que.push(S);
while(!que.empty()){
int now=que.front();
que.pop();
vis[now]=;
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]]=;
que.push(to1[i]);
}
}
}
}
void spfa1(int S){
queue<int>que;
memset(vis,,sizeof(vis));
memset(dis,0x7f,sizeof(di));
vis[S]=;dis[S]=val1[S];
que.push(S);
while(!que.empty()){
int now=que.front();
que.pop();
vis[now]=;
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]]=;
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=;i<=n;i++) val[i]=read();
for(int i=;i<=m;i++){
int u=read();
int v=read();
int w=read();
add(u,v,w);
}
for(int i=;i<=n;i++)
if(!vis[i]) tarjin(i);
for(int i=;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]]]=;
add2(col[i],col[to[j]],cap[j]);
add3(col[to[j]],col[i],cap[j]);
}
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
if(!vis[col[i]]) val1[col[i]]=val[i],vis[col[i]]=;
else val1[col[i]]=(val1[col[i]]&val[i]);
for(int i=;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 ; }
else{ printf("%d\n",min(di[col[t]],dis[col[s]]));return ; }
}
70tarjin缩点+正反跑spfa
/*
————该题目主要考察tarjan缩点，拓扑排序和贪心
40pts:
直接爆搜，看每条边走不走，复杂度 ，此部分分贪心将所有权值&起来是有分的（给对题目做了一定分析的盆友的彩蛋）
60pts:
对于M = N - 1的点，其实他并不是树QWQ，因为题目中明确说了不保证联通，所以这个部分分是个假的。但是为了多给大家送点分，此部分数据采用随机生成，不论是用不正确的spfa还是dijkstra都能够跑过去，是不是很良心。
80pts：
考虑每个联通分量中，能走的肯定要尽量去走，然后我们缩点求出连通分量的贡献，转换成DAG上的问题，然后发现DAG上不能够简单地按照拓扑序取min做dp转移，但是我们可以对DAG上每一个位置开一个64的数字记录到这个节点各个数字是否可行，然后拓扑序转移，复杂度64（N + M) 还是能跑过去的
100pts：
既然每个二进制位上的数字互不干扰，我们就拆分二进制做。
考虑从高位向低位枚举二进制位，我们肯定是希望高位上能够为0，那么我们考虑在整个DAG中的那些路径是能够使这一位为0的，显然，在所有从s到t的道路中，若存在某个点或者边，那么他所有的后继路径和前驱路径都是可行的，那么我们可以正反拓扑两次找到所有可行的点边集合作为当前答案。
然后考虑下一位，下一位中因为要保证上一位是0，所以能够走的点和边肯定是上次得到的点边集合里的，我们在这个得到的集合中在尽行同样的拓扑看看当前位是否可行，如果可行的话就用新得到的点边集合去更新原图的点边集合。
如此做三十次考虑所有的为就能得到答案了。
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#include<ctime>
#include<cmath>
#include<set>
#include<map>
#define ll long long
#define M 700010
struct Edge {
int vi, vj, v;
} edge[M];
struct Note {
int vj, v, id;
} be;
using namespace std;
int read() {
int nm = , f = ;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -;
for(; isdigit(c); c = getchar()) nm = nm * + c - '';
return nm * f;
}
vector<int>to[M];
vector<Note> to1[M], to2[M];
int belong[M], st[M], dfn[M], low[M], dft, n, m, s, t, note[M], noww[M], tp, tot, sz[M], ans = , rudu1[M], rudu2[M];
bool vis[M];
void tarjan(int now) {
vis[now] = true;
st[++tp] = now;
dfn[now] = low[now] = ++dft;
for(int i = ; i < to[now].size(); i++) {
int vj = to[now][i];
if(!dfn[vj]) {
tarjan(vj);
low[now] = min(low[now], low[vj]);
} else if(vis[vj]) low[now] = min(low[now], dfn[vj]);
}
if(dfn[now] == low[now]) {
tot++;
while(st[tp] != now) {
int x = st[tp];
vis[x] = false;
noww[tot] &= note[x];
belong[x] = tot;
tp--;
}
int x = st[tp];
vis[x] = false;
noww[tot] &= note[x];
belong[x] = tot;
tp--;
}
}
bool can[M], tmp1[M], tmp2[M];
int note1[M], note2[M], tp1, tp2; void tuopu() {
queue<int>q;
q.push(belong[t]);
while(!q.empty()) {
int op = q.front();
q.pop();
for(int i = ; i < to2[op].size(); i++) {
int vj = to2[op][i].vj;
rudu2[vj]++;
if(!vis[vj]) q.push(vj), vis[vj] = true;
}
}
while(!q.empty()) q.pop();
q.push(belong[s]);
while(!q.empty()) {
int op = q.front();
note1[++tp1] = op;
q.pop();
for(int i = ; i < to1[op].size(); i++) {
int vj = to1[op][i].vj;
rudu1[vj]--;
if(rudu1[vj] == ) q.push(vj);
}
}
q.push(belong[t]);
while(!q.empty()) {
int op = q.front();
q.pop();
note2[++tp2] = op;
for(int i = ; i < to2[op].size(); i++) {
int vj = to2[op][i].vj;
rudu2[vj]--;
if(rudu2[vj] == ) q.push(vj);
}
}
} void work(int x) {
for(int i = ; i <= tot; i++) tmp1[i] = tmp2[i] = false;
if((noww[belong[s]] & x) == ) tmp1[belong[s]] = true;
for(int i = ; i <= tp1; i++) {
int op = note1[i];
for(int j = ; j < to1[op].size(); j++) {
be = to1[op][j];
if((tmp1[op] == true) || (can[be.id] && ((be.v & x) == ))) {
tmp1[be.vj] = true;
tmp1[be.id] = true;
} else if((noww[be.vj] & x) == && (can[be.vj])) tmp1[be.vj] = true;
}
}
if((noww[belong[t]] &x) == ) tmp2[belong[t]] = true;
for(int i = ; i <= tp2; i++) {
int op = note2[i];
for(int j = ; j < to2[op].size(); j++) {
be = to2[op][j];
if((tmp2[op] == true) || (can[be.id] && ((be.v & x) == ))) {
tmp2[be.vj] = true;
tmp2[be.id] = true;
} else if((noww[be.vj] & x) == && (can[be.vj])) tmp2[be.vj] = true;
}
}
for(int i = ; i <= tot; i++) tmp1[i] = (tmp1[i] | tmp2[i]);
if(tmp1[belong[s]] && tmp1[belong[t]]) ans -= x;
else return;
for(int i = ; i <= tot; i++) can[i] = (can[i] & tmp1[i]);
}
int main() {
freopen("rabbit.in", "r", stdin);
freopen("rabbit.out", "w", stdout);
cin >> n >> m >> s >> t;
for(int i = ; i <= n; i++) note[i] = read(), noww[i] = ;
for(int i = ; i <= m; i++) {
int vi = read(), vj = read(), v = read();
edge[i].vi = vi, edge[i].vj = vj, edge[i].v = v;
to[vi].push_back(vj);
}
tarjan(s);
if(!dfn[t]) {
puts("-1");
return ;
}
for(int i = ; i <= m; i++) {
int vi = edge[i].vi, vj = edge[i].vj, v = edge[i].v;
vi = belong[vi], vj = belong[vj];
if(vi == || vj == ) continue;
if(vi == vj) noww[vi] &= v;
else {
be.id = ++tot;
be.vj = vj;
be.v = v;
to1[vi].push_back(be);
rudu1[vj]++;
be.vj = vi;
to2[vj].push_back(be);
}
}
if(belong[s] == belong[t]) {
cout << noww[belong[s]] << "\n";
return ;
}
tuopu();
for(int i = ; i <= tot; i++) can[i] = true;
for(int i = ; i >= ; i--) work( << i);
cout << ans << "\n";
return ;
}
std