思路清奇的一道题
READ MORE →
BZOJ2597
T飞了……
前排膜拜PoPoQQQ大神的题解
反正我的SPFA费用流是T飞了……
估计因为不停的memset 一共 \( n^2 \) 次然后就炸了吧
:-(等我学个ZKW的姿势回来再切这道题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
#include <cstdio> #include <algorithm> #include <cstring> #define ll long long #define INF 100000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> inline void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #define ququq 100000 char bsd[ququq]; int last; inline void output() { puts(bsd); } inline void add(int x,char lc) { static char c[12]; static int node; if(x==0) { bsd[last++]='0';bsd[last++]=lc; return; } node=0; while(x) c[node++]=x%10,x/=10; while(node) bsd[last++]=c[--node]+'0'; bsd[last++]=lc; } using namespace std; #define N 110 #define SIZ 10200 #define S 0 #define T 10199 struct Tedge { int from,to,flow,val; }edge[SIZ<<6]; #define E edge[i] #define TO E.to #define FROM E.from #define FLOW E.flow #define VAL E.val int fst[SIZ],NXT[SIZ<<6],e_tot; void add_e(int from,int to,int cap,int val) { static int &i=e_tot; FROM=from; TO=to; FLOW=cap; VAL=val; NXT[e_tot]=fst[from]; fst[from]=e_tot++; FROM=to; TO=from; FLOW=0; VAL=val; NXT[e_tot]=fst[to]; fst[to]=e_tot++; } int mp[N][N],n,A_[N][N],ans[N][N]; int calc(int i,int j) { if(i>j) swap(i,j); return (i-1)*n+j; } inline void init() { memset(fst,-1,sizeof(fst)); read(n); For(i,1,n) for(int j=1;j<=n;j++) read(mp[i][j]); For(i,1,n) for(int j=0;j<n-1;j++) add_e(S,i,1,j); For(i,1,n) for(int j=1;j<=n;j++) { if(i==j) continue; if(i<j)add_e(calc(i,j)+n,T,1,0); if(mp[i][j]==1||mp[i][j]==2) { add_e(j,calc(i,j)+n,1,0); A_[i][j]=e_tot-1; } } } int p[SIZ],dis[SIZ],ANS; bool inq[SIZ]; void cp(int &x,int y) { x>y?x=y:x=x; } void Augment() { static int node,c,i; node=T; c=INF; while(node!=S) { i=p[node]; cp(c,FLOW); node=FROM; } node=T; while(node!=S) { i=p[node]; FLOW-=c; i^=1; FLOW+=c; node=TO; } ANS-=c*dis[T]; } bool SPFA() { static int x,Q[65540],i; static unsigned short int he=0,ta=0; memset(dis,0x7f,sizeof(dis)); Q[++he]=S; dis[S]=0; inq[S]=true; while(he!=ta) { x=Q[++ta]; inq[x]=false; for(i=fst[x];~i;i=NXT[i]) { if(!FLOW||dis[TO]<=dis[x]+VAL) continue; dis[TO]=dis[x]+VAL; p[TO]=i; if(!inq[TO]) { dis[TO]<dis[Q[ta+1]]?Q[ta--]=TO:Q[++he]=TO; inq[TO]=true; } } } return (dis[T]>INF)?false:true; } int main() { freopen("BZOJ2597.in","r",stdin); init(); ANS=n*(n-1)*(n-2)/6; while(SPFA()) Augment(); add(ANS,'\n'); For(i,1,n) for(int j=1;j<=n;j++) add(!A_[i][j]||!edge[A_[i][j]].flow?0:1,j==n?'\n':' '); output(); return 0; } |
BZOJ4869
这道题是这样子的……一个区间求和一个区间加幂
之前刚刚学了降幂大法就是为了写这道题:-D
然后就直接肝……当然最后还要展开多一层的1[EXM?]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
#include <cstdio> #include <algorithm> #include <cstring> #define ll long long #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 100010 int f[50],tmp; int n,m,p,c; int Arr[N],time[N]; bool b[N]; int pri[N],tot; int calc_phi(int x) { int ret=x; for(int i=0;pri[i]*pri[i]<=x&&i<tot;i++) if(x%pri[i]==0) { ret-=ret/pri[i]; while(x%pri[i]==0) x/=pri[i]; } if(x>1) ret-=(ret/x); return ret; } int ksm(int x,int top,int mod,bool &pp) { int ret=1; bool ccc=false; for(;top;top>>=1) { if(top&1) pp|=ccc|(1LL*ret*x>=mod),ret=1LL*ret*x%mod; ccc=1LL*x*x>=mod; x=1LL*x*x%mod; } return ret; } int solve(int a,int L) { bool pp=(a>=f[L]); int mmp=a%f[L]; for(;L;L--) mmp=ksm(c,mmp+(pp?f[L]:0),f[L-1],pp); return mmp; } struct node { int l,r,c[2],sum; bool is; }pool[N<<2]; int pcnt; #define Lc pool[x].c[0] #define Rc pool[x].c[1] #define L pool[x].l #define R pool[x].r #define SUM pool[x].sum #define TIME time[L] #define IS pool[x].is inline void PushUP(int x) { SUM = pool[Lc].sum+pool[Rc].sum; SUM>=p?SUM-=p:SUM; IS=pool[Lc].is&pool[Rc].is; } void build(int l,int r,int x) { L=l; R=r; if(l==r) { SUM=Arr[l]%p; IS=(time[l]==tmp); return; } int mid = (l+r) >>1; build(l,mid,Lc=++pcnt); build(mid+1,r,Rc=++pcnt); PushUP(x); } void rebuild(const int &l,const int &r,int x) { if(IS) return; if(L==R) { TIME++; SUM=solve(Arr[L],TIME); IS=(TIME==tmp); return; } int mid=(L+R)>>1; if(mid>=l) rebuild(l,r,Lc); if(mid <r) rebuild(l,r,Rc); PushUP(x); } int query(const int& l,const int& r,int x) { if(l<=L&&R<=r) return pool[x].sum; if(R<l||L>r) return 0; int ret=0; int mid = (L+R)>>1; ret+=query(l,r,Lc); ret+=query(l,r,Rc); return ret>=p?ret-p:ret; } void pre() { for(int i=1;i<=n;i++) read(Arr[i]); int x=p; for(int i=2;i*i<=p;i++) { !b[i]?pri[tot++]=i:b[i]; for(int j=0;j<tot&&pri[j]*i<N;j++) { b[pri[j]*i]=1; if(i%pri[j]==0) break; } } while(x>1) f[tmp++]=x,x=calc_phi(x); f[tmp++]=1; f[tmp]=1; build(1,n,0); } int main() { freopen("BZOJ4869.in","r",stdin); read(n); read(m); read(p); read(c); pre(); static int a,l,r; while(m--) { read(a); read(l); read(r); if(a) printf("%d\n",query(l,r,0)); else(rebuild(l,r,0)); } return 0; } |
BZOJ4810 莫队+bitset
题目 链接 ：http://www.lydsy.com/JudgeOnline/problem.php?id=4810
kry大爷的代码好短……可以看看orz
这题目测只要是根号+压位就能过得去的了……所以不要太在意细节
[然后就被细节骗走了五次wa]
如果我们压了位……
减法就可以直接右移解决 b-c=a
加法的话把它反过来右移解决 大概是变成 a+b=c -> b-c=-a
乘法很simple，直接暴力就好了，根号可是比n/64要小的
而且时限30s，跑起来好像还挺稳的？
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <bitset> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 100010 #define SIZ 400 bitset <N> Appear,Rev,____; int a[N],cnt[N],n,m; int l[SIZ],r[SIZ],belong[N],SQR,CNT; struct rec { int l,r,c,type; int id; }pool[N]; bool comp(const rec &x,const rec&y ) { if(belong[x.l]==belong[y.l]) return x.r<y.r; return x.l<y.l; } void pre() { read(n); read(m); for(int i=1;i<=n;i++) read(a[i]); SQR=sqrt(n); CNT=(n-1)/SQR+1; for(int i=1;i<=CNT;i++) { l[i]=(CNT-1)*SQR+1; r[i]=CNT*SQR; } r[CNT]=n; for(int i=1;i<=n;i++) belong[i]=(i-1)/SQR+1; for(int i=1;i<=m;i++) { read(pool[i].type); read(pool[i].l); read(pool[i].r); read(pool[i].c); pool[i].id=i; } sort(pool+1,pool+1+m,comp); } int ans[N]; void solve(int i) { if(pool[i].type==1) { ____=Appear; ____>>=pool[i].c; ____&=Appear; if(____.any()) ans[pool[i].id]=1; else ans[pool[i].id]=0; return; } if(pool[i].type==2) { ____=Rev; ____>>=(100000-pool[i].c); ____&=Appear; if(____.any()) ans[pool[i].id]=1; else ans[pool[i].id]=0; return; } if(pool[i].type==3) { for(int j=1;j*j<=pool[i].c;j++) if(cnt[j]&&cnt[pool[i].c/j]) { if(pool[i].c%j==0) { ans[pool[i].id]=1; return; } } ans[pool[i].id]=0; return; } } int main() { pre(); int nodeR,nodeL; nodeR=0;nodeL=1; for(int i=1;i<=m;i++) { while(nodeR<pool[i].r) { nodeR++; cnt[a[nodeR]]++; if(cnt[a[nodeR]]==1) Appear[a[nodeR]]=1,Rev[100000-a[nodeR]]=1; } while(nodeL>pool[i].l) { nodeL--; cnt[a[nodeL]]++; if(cnt[a[nodeL]]==1) Appear[a[nodeL]]=1,Rev[100000-a[nodeL]]=1; } while(nodeL<pool[i].l) { cnt[a[nodeL]]--; if(!cnt[a[nodeL]]) Appear[a[nodeL]]=0,Rev[100000-a[nodeL]]=0; nodeL++; } while(nodeR>pool[i].r) { cnt[a[nodeR]]--; if(!cnt[a[nodeR]]) Appear[a[nodeR]]=0,Rev[100000-a[nodeR]]=0; nodeR--; } solve(i); } for(int i=1;i<=m;i++) ans[i]?puts("yuno"):puts("yumi"); return 0; } |