首页 > 代码库 > Codeforces Round #371 (Div. 1)
Codeforces Round #371 (Div. 1)
A：
题目大意：
在一个multiset中要求支持3种操作：
1.增加一个数
2.删去一个数
3.给出一个01序列,问multiset中有多少这样的数,把它的十进制表示中的奇数改成1,偶数改成0后和给出的01序列相等(比较时如果长度不等各自用0补齐)
题解：
1.我的做法是用Trie数来存储,先将所有数用0补齐成长度为18位,然后就是Trie的操作了。
2.官方题解中更好的做法是,直接将每个数的十进制表示中的奇数改成1,偶数改成0,比如12345,然后把它看成二进制数10101,还原成十进制是21,然后cnt[21]++,求答案的时候只要把01序列看成二进制数,然后转换成十进制x,cnt[x]就是答案。
我的代码(Trie做法)
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <vector>#include <map>#include <cstdlib>#include <set>using namespace std;#define X first#define Y second#define N 1000010typedef long long ll;typedef pair<int,int> pii;int n,tot=1;int cnt[N],ch[N][2];void Add(int x,ll val,int k,int op){ cnt[x]+=op; if (k==0) return; int v=(val%10)&1; if (!ch[x][v]) ch[x][v]=++tot; Add(ch[x][v],val/10,k-1,op);}int Query(int x,ll val,int k){ if (k==0) return cnt[x]; int v=(val%10)&1; if (!ch[x][v]) return 0; return Query(ch[x][v],val/10,k-1);}int main(){ //freopen("in.in","r",stdin); //freopen("out.out","w",stdout); scanf("%d",&n); char op; ll x; for (int i=1;i<=n;i++) { scanf(" %c%I64d",&op,&x); if (op==‘+‘) Add(1,x,18,1); if (op==‘-‘) Add(1,x,18,-1); if (op==‘?‘) printf("%d\n",Query(1,x,18)); } return 0;}
B：
题目大意：
在一个n*n的矩形中,有2个没有公共边也不重叠的矩形,然后最多可以询问200次,每次询问一个矩形中有多少个矩形(会给出答案0或1或2),要求找到这两个矩形的位置。
题解：
1.如果只有一个矩形,显然可以用二分确定它的坐标。所以基本思想是找到一条分界线 将这两个矩形分开,然后各自独立寻找位置。
2.对于这两个矩形,要么是左右关系,要么是上下关系。如果是左右关系,我们先确定询问的左边界,上边界和下边界,然后逐步增大右边界,那么矩形的个数肯定是从0到1到2递增的,所以可以二分出这个 分界线。 上下关系同理。 具体实现看代码。
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <vector>#include <map>#include <cstdlib>#include <set>using namespace std;#define X first#define Y second#define Mod 1000000007#define N 100010typedef long long ll;typedef pair<int,int> pii;int xx1,yy1,xx2,yy2,X1,Y1,X2,Y2;int Check(int x1,int y1,int x2,int y2){ printf("? %d %d %d %d\n",x1,y1,x2,y2); fflush(stdout); int x; scanf("%d",&x); return x;}void Solve(int l,int d,int r,int u){ int L,R,Mid,x1,y1,x2,y2; L=d,R=u; while (L<R) { Mid=(L+R)>>1; if (Check(l,d,r,Mid)==0) L=Mid+1; else R=Mid; } y2=L; L=d,R=u; while (L<R) { Mid=(L+R+1)>>1; if (Check(l,Mid,r,u)==0) R=Mid-1; else L=Mid; } y1=L; L=l,R=r; while (L<R) { Mid=(L+R)>>1; if (Check(l,d,Mid,u)==0) L=Mid+1; else R=Mid; } x2=L; L=l,R=r; while (L<R) { Mid=(L+R+1)>>1; if (Check(Mid,d,r,u)==0) R=Mid-1; else L=Mid; } x1=L; if (!xx1) xx1=x1,yy1=y1,xx2=x2,yy2=y2; else X1=x1,Y1=y1,X2=x2,Y2=y2;}int main(){ //freopen("in.in","r",stdin); //freopen("out.out","w",stdout); int n,L,R,Mid; scanf("%d",&n); L=1,R=n; while (L<R) { Mid=(L+R)>>1; if (Check(1,1,Mid,n)>=1) R=Mid; else L=Mid+1; } if (Check(1,1,L,n)==1 && Check(L+1,1,n,n)==1) { Solve(1,1,L,n); Solve(L+1,1,n,n); } else { L=1,R=n; while (L<R) { Mid=(L+R)>>1; if (Check(1,1,n,Mid)>=1) R=Mid; else L=Mid+1; } Solve(1,1,n,L); Solve(1,L+1,n,n); } printf("! %d %d %d %d %d %d %d %d\n",xx1,yy1,xx2,yy2,X1,Y1,X2,Y2); fflush(stdout); return 0;}
C：
题目大意：
给出一个长度为n的数列(n<=3000),每次操作可以把其中一个数增大1或者减小1,求最少操作次数使得数列单调增。
题解：
1.首先一个转化： $a_i<a_{i+1} <--> a_i-i<=a_{i+1}-(i+1)$ 所以把所有$a_i$减去$i$就转化为单调不减,就和POJ3666一样了。
具体可以看 http://www.cnblogs.com/vb4896/p/5877962.html
代码：
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <vector>#include <map>#include <cstdlib>#include <set>using namespace std;#define X first#define Y second#define Mod 1000000007#define N 3010typedef long long ll;typedef pair<int,int> pii;inline int Mul(int x,int y){return 1ll*x*y%Mod;}inline int Add(int x,int y){return ((x+y)%Mod+Mod)%Mod;}int n,m;int a[N],b[N];ll dp[N][N],Ans=1ll<<60;void Solve(){ for (int j=1;j<=m;j++) dp[1][j]=abs(b[j]-a[1]); for (int i=2;i<=n;i++) { ll tmp=1ll<<60; for (int j=1;j<=m;j++) { tmp=min(tmp,dp[i-1][j]); dp[i][j]=abs(b[j]-a[i]); dp[i][j]+=tmp; } } for (int j=1;j<=m;j++) Ans=min(Ans,dp[n][j]);}int main(){ //freopen("in.in","r",stdin); //freopen("out.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]=a[i]-i; sort(b+1,b+n+1); for (int i=1;i<=n;i++) if (i==1 || b[i]!=b[i-1]) b[++m]=b[i]; Solve(); printf("%I64d\n",Ans); return 0;}
D：
题目大意：
给出n*m的01矩阵,最多1e6个询问,每次询问一个子矩形中最大的全1正方形的边长。
题解
1.首先可以dp出以(i,j)为左下角的最大正方形边长,dp[i][j]=max{dp[i+1][j+1],dp[i+1][j],dp[i][j+1]}+1.当然如果(i,j)格是0 那dp[i][j]=0.
2.考虑二分答案。二分时检查矩形(x1,y1)-(x2-Mid+1,y2-Mid+1)里的dp值是否有大于等于Mid的。 区间的最大值可以用二维RMQ解决...第一次写,竟然写对了。然后想起前几天学了个用树状数组求区间最大值的方法，就想把它也扩展到二维,写到一半发现剧难写,再加上这几天心不是很静,弃疗了。
还是贴个RMQ的代码吧。
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <vector>#include <map>#include <cstdlib>#include <set>using namespace std;#define X first#define Y second#define Mod 1000000007#define N 1010#define Inf 1000000007typedef long long ll;typedef pair<int,int> pii;int n,m,Q;int v[N][N],dp[N][N],sum[N][N];int f[N][N][11][11];void Build(){ for (int p=0,l1=1;l1<=n;l1<<=1,p++) { for (int q=0,l2=1;l2<=m;l2<<=1,q++) { if (p+q==0) continue; for (int i=1;i+l1-1<=n;i++) { for (int j=1;j+l2-1<=m;j++) { if (p!=0) f[i][j][p][q]=max(f[i][j][p-1][q],f[i+(l1>>1)][j][p-1][q]); else f[i][j][p][q]=max(f[i][j][p][q-1],f[i][j+(l2>>1)][p][q-1]); } } } }}int Getmax(int x1,int y1,int x2,int y2){ int p=0,l1=1,q=0,l2=1,tmp1,tmp2; while (l1<=x2-x1+1) l1<<=1,p++; p--,l1>>=1; while (l2<=y2-y1+1) l2<<=1,q++; q--,l2>>=1; tmp1=max(f[x1][y1][p][q],f[x1][y2-l2+1][p][q]); tmp2=max(f[x2-l1+1][y1][p][q],f[x2-l1+1][y2-l2+1][p][q]); return max(tmp1,tmp2);} int main(){ //freopen("in.in","r",stdin); //freopen("out.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { scanf("%d",&v[i][j]); sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+v[i][j]; } for (int i=n;i>=1;i--) { for (int j=m;j>=1;j--) { if (v[i][j]==0) dp[i][j]=0; else dp[i][j]=min(min(dp[i+1][j+1],dp[i][j+1]),dp[i+1][j])+1; f[i][j][0][0]=dp[i][j]; } } Build(); int L,R,Mid,x1,y1,x2,y2; scanf("%d",&Q); while (Q--) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if (sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]==0) printf("0\n"); else { L=1,R=min(x2-x1+1,y2-y1+1); while (L<R) { Mid=(L+R+1)>>1; if (Getmax(x1,y1,x2-Mid+1,y2-Mid+1)>=Mid) L=Mid; else R=Mid-1; } printf("%d\n",L); } } return 0;}
Codeforces Round #371 (Div. 1)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。