好久没有写博客了...
言归正传奥
T1就是个送分题...
#include <cstdio> #include <cstring> #include <iostream> #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int n,maxp; ll a[26],b[26],c[26],d[26]; ll ans; int main(){ freopen("week.in","r",stdin); freopen("week.out","w",stdout); scanf("%d",&n); maxp=(1<<n)-1; for(int i=1;i<=n;++i) scanf("%lld%lld%lld%lld",&a[i],&b[i],&c[i],&d[i]); ll temp,oi,wen; for(int i=0;i<=maxp;++i) { oi=0;wen=0; for(int j=1;j<=n;++j) { if( (1<<(j-1))&i ) { oi+=c[j]; wen-=d[j]; if(wen<0) wen=0; } else { wen+=a[j]; oi-=b[j]; if(oi<0) oi=0; } } temp=oi*wen; if(ans<temp) ans=temp; } cout<<ans; }
T2
用到了一个性质：
在一个无环图里，联通快个数=点数-边数 （证明很显然啊啊啊）
然后维护出 点和边数的前缀和就完了...
#include <cstdio> #include <cstring> #include <iostream> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int readdan() { char q=getchar(); while(q!='0'&&q!='1')q=getchar(); return q-'0'; }; const int N=2006; int n,m,Q; int a[N][N]; int d[N][N]; int by[N][N],bx[N][N],b[N][N]; void chu() { for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j]; int con,conx; for(int i=1;i<=n;++i) { con=0;conx=0; for(int j=1;j<=m;++j) { if(a[i][j]&&a[i][j-1]) ++con; if(a[i][j]&&a[i-1][j]) ++con; if(a[i][j]&&a[i+1][j]) ++conx; b[i][j]=b[i-1][j]+con; bx[i][j]=conx; by[i][j]=by[i-1][j]+( (a[i][j]&&a[i][j+1])?1:0 ); } } } void out11() { printf(" "); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) printf("%d ",b[i][j]); printf(" "); } printf(" "); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) printf("%d ",bx[i][j]); printf(" "); } printf(" "); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) printf("%d ",by[i][j]); printf(" "); } printf(" "); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) printf("%d ",d[i][j]); printf(" "); } printf(" "); } int main(){ freopen("T2.in","r",stdin); scanf("%d%d%d",&n,&m,&Q); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]=readdan(); chu(); //out11(); int lx,ly,rx,ry; for(int i=1;i<=Q;++i) { scanf("%d%d%d%d",&lx,&ly,&rx,&ry); int tb,td; tb=b[rx][ry]-b[lx-1][ry]-b[rx][ly-1]+b[lx-1][ly-1]-(by[rx][ly-1]-by[lx-1][ly-1])-(bx[lx-1][ry]-bx[lx-1][ly-1]); td=d[rx][ry]-d[lx-1][ry]-d[rx][ly-1]+d[lx-1][ly-1]; printf("%d ", td-tb ); } }
T3
脑洞打开的数学题 （然而我的脑洞并没有打开啊...）
题解在代码里
/* 这个题真是 考(kao)思(nao)维(dong) 实际上是求个逆序对 然后根据规律 发现是个 等差数列 然后就找规律吧... */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cstdlib> #define ll long long using namespace std; const int MAXA=100006; int tin1,a,mod,n; ll c[MAXA]; void add(int val) { for(int i=val;i<MAXA;i+=(i&(-i)) ) ++c[i]; } ll qq(int val) { ll ans=0; for(int i=val;i>0;i-=(i&(-i)) ) ans+=c[i]; return ans; } ll work() { ll ans=0; int fir=tin1+1; int num1=(mod-fir)/a+1; ll temp,num=-1,temp1,las=-1,firtot=(mod-fir)/a+1; int now=fir+a*(num1-1); //printf("firtot=%lld num1=%d ",firtot,num1); for(int i=num1+1;i<=n;++i) { now+=a; if(now>mod) { ++num; now-=mod; las=-1; } //printf("i=%d now=%d num=%lld las=%lld ",i,now,num,las); if(las==-1) { temp=i-1-qq(now)-num1; //printf("temp=%lld ",temp); if(now>fir) ans+=( firtot- ( (now-fir)/a+1 ) ); else ans+=firtot; //printf("ans1=%lld ",ans); ans+=temp; //printf("ans2=%lld ",ans); las=temp; } else { las-=num; ans+=las; if(now>fir) ans+=( firtot- ( (now-fir)/a+1 ) ); else ans+=firtot; } if(now<=a)add(now); //printf("ans=%lld ",ans); } // 5 2 4 7 return ans; } int main(){ //freopen("T3.in","r",stdin); scanf("%d%d%d%d",&n,&tin1,&a,&mod); cout<<work(); }
简单总结一下：
这次考试暴力分挺多，我也就拿了个 暴力分
思维含量 在 T2和T3 里
所以说 我思维还是要锻炼一下啊 （然而std表示 wocao这题怎么这么简单）
以后不管做题还是走路还是吃饭还是睡觉，还是不能走思啊啊啊啊