UVALive 4493 That is Your QueueUVALive 4494 How Many Ones NeededUVALive 4495 Foot NotesUVALive 4496 A Match Making ProblemUVALive 4497 Games of BlockUVALive 4502 How Many bases

UVALive 4493 That is Your Queue

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (200000+10) int n,m; int q[MAXN],l=100000; int b[MAXN]={0}; int main() { // freopen("A.in","r",stdin); // freopen(".out","w",stdout); int kc=1; while(cin>>n>>m&&n&&m) { printf("Case %d:\n",kc++); MEM(b) int l=100000,r=100000-1; if (n>5000) n=5000; For(i,n) q[++r]=i,b[r]=1; For(i,m) { char s[2]; scanf("%s",s); if (s[0]=='N') { while(!b[l]) ++l; cout<<q[l]<<endl; b[l]=0; b[r+1]=1; q[++r]=q[l]; l++; } else { int p=read(); Fork(i,l,r) if (b[i]&&q[i]==p){ b[i]=0; } q[--l]=p;b[l]=1; } } } return 0; }

UVALive 4494 How Many Ones Needed?

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (2000000000+10) ll n,m; ll calc(ll n) { ll p=2,ans=0; For(i,35) { ll t1=n/p,t2=n%p; ans+=p/2*t1; if (p/2<=t2) { ans+=t2-p/2+1; } p*=2LL; } return ans; } int main() { // freopen("B.in","r",stdin); // freopen(".out","w",stdout); int kc=1; // For(i,10) cout<<calc(i)<<endl; while(cin>>n>>m) { if (n==0&&m==0) break; printf("Case %d: ",kc++); cout<<calc(m)-calc(n-1)<<endl;; } return 0; }

UVALive 4495 Foot Notes

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (510) int n,s,m; vi c[MAXN]; bool b[MAXN]; int f[MAXN][MAXN]; int h[MAXN]; ll calc() { For(i,n) if (f[i][i]+1>s) return -1; h[1]=f[1][1]; For(i,n) { h[i]=INF; if (i+f[1][i]<=s) h[i]=f[1][i]; For(j,i-1) if (f[j+1][i]+i-j<=s) h[i]=min(h[i],h[j]+f[j+1][i]); } return h[n]; } int main() { // freopen("C.in","r",stdin); // freopen(".out","w",stdout); int T=read(); For(kcase,T) { printf("Case %d: ",kcase); n=read(),s=read(),m=read(); For(i,m) { int k=read(); while(k--) c[read()].pb(i); } For(i,n) { MEM(b) int ans=0; Fork(j,i,n) { int sz=SI(c[j]); for(int k=0;k<sz;k++) if (!b[c[j][k]]) { ans++; b[c[j][k]]=1; } f[i][j]=ans; } } cout<<calc()<<endl; For(i,n) c[i].clear(); } return 0; }

UVALive 4496 A Match Making Problem

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (70) int c[MAXN],c2[MAXN]; int main() { // freopen("D.in","r",stdin); // freopen(".out","w",stdout); int n,m,kcase=1; while(cin>>n>>m&&n&&m) { MEM(c) MEM(c2) For(i,n) c[read()]++; For(i,m) c2[read()]++; ForD(i,60) if (c[i]) { } printf("Case %d: ",kcase++); if (n<=m) puts("0"); else { cout<<n-m<<' '; For(i,60) if (c[i]) { cout<<i<<endl; break; } } } return 0; }

UVALive 4497 Games of Block

Aplha-beta剪枝，TLE 打表，代码长度限制 把最慢的几个点打表，终于过了

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } bool inside(int i,int j) {return 0<=i&&i<4&&0<=j&&j<4;} int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; struct P { int a[4][4]; int l; bool isFinal() { Rep(i,4) Rep(j,4) if (a[i][j]) return 0; return 1; } void init() { Rep(i,4) { char s[10]; scanf("%s",s); Rep(j,4) a[i][j]=(s[j]=='B')?(1):(2); } l=0; } void drop() { bool fl=1; while(fl) { fl=0; Rep(i,3) Rep(j,4) if (a[i+1][j]==0&&a[i][j]!=0) swap(a[i][j],a[i+1][j]),fl=1; } } void mem(int i,int j,int p,int vis[4][4]) { a[i][j]=0; vis[i][j]=1; Rep(di,4) { int x=i+dir[di][0],y=j+dir[di][1]; if (!inside(x,y)) continue; if (a[x][y]==p) mem(x,y,p,vis); } } void expand(vector<P> &t) { int vis[4][4]={0}; Rep(i,4) Rep(j,4) if(a[i][j]&&!vis[i][j]){ P now=*this; now.mem(i,j,a[i][j],vis); now.drop(); now.l++; t.pb(now); } } void pri() { Rep(i,4) { Rep(j,4) cout<<a[i][j];cout<<endl; } cout<<endl; } int calc() { int an=0; Rep(i,4) { Rep(j,4) { int p=1<<(i*4+j); if (a[i][j]==1) an+=p; } } return an; } }S; //map< mp( mp(s,player),alpha, const int inf = 10000; int alphabeta(P& s,int player,int alpha,int beta) { if (s.isFinal()) { if (!player) return -inf+s.l; return inf-s.l; } vector<P> children; s.expand(children); int n=children.size(); Rep(i,n) { int v=alphabeta(children[i],player^1,alpha,beta); if (!player) alpha=max(alpha,v); else beta=min(beta,v); if(beta<=alpha) break; } return (!player)?alpha:beta; } int sol[1<<16]={0}; int main() { // freopen("e.in","r",stdin); // freopen("data.out","w",stdout); int T=read(); int kc=1; sol[9637]=inf-7; sol[23130]=-inf+10; sol[42405]=-inf+10; sol[55898]=inf-7; while(T--) { printf("Case %d: ",kc++); S.init(); int p,now=S.calc(); if (sol[now]) { p=sol[now]; } else sol[now]=p=alphabeta(S,0,-INF,INF); bool fl=(p>0); if (fl) cout<<"win "<<inf-p; else cout<<"loss "<<inf+p; puts(""); } return 0; }

UVALive 4502 How Many bases?

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (100000+10) int n,m,t; int p[MAXN],tot; bool b[MAXN]={0}; void make_prime(int n) { tot=0; Fork(i,2,n) { if (!b[i]) p[++tot]=i; For(j,tot) { if (i*p[j]>n) break; b[i*p[j]]=1; if (i%p[j]==0) break; } } } void work(vector<int > &t,int n) { For(i,tot) { if (n<p[i]) break; if (n%p[i]==0) { int c=0; while(n%p[i]==0) { n/=p[i]; c++; } t.pb(c); } } if (n>1) t.pb(1); } ll calc(vi c,int n,int T) { ll ans=1; Rep(i,n) { // cout<<c[i]<<endl; ans=mul(ans,c[i]*m/T+1); } return ans; } int main() { // freopen("J.in","r",stdin); // freopen(".out","w",stdout); int kc=1; make_prime(10000); while(cin>>n>>m>>t) { if (n==0&&m==0&&t==0) break; printf("Case %d: ",kc++); vector<int> c; work(c,n); int sz=SI(c); ll ans=sub(calc(c,sz,t),calc(c,sz,t+1)); cout<<ans<<endl; } return 0; }