Codeforces Round #545 (Div. 1)-白红宇

Codeforces Round #545 (Div. 1)

阅读量：5833 次

发布时间：2019-06-18

本文共 9065 字，大约阅读时间需要 30 分钟。

A - Skyscrapers

暴力离散化之后再乱搞一搞就好了。

#include
    
     #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vi vector
     
      #define vit vector
      
       ::iterator#define pir pair
       
        #define fr first#define sc second#define mp(x,y) make_pair(x,y)using namespace std;inline char gc() {//  static char buf[100000],*p1,*p2;//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;    return getchar();}template
        
         int read(T &ans) {    ans=0;char ch=gc();T f=1;    while(!isdigit(ch)) {        if(ch==EOF) return -1;        if(ch=='-') f=-1;        ch=gc();    }    while(isdigit(ch))        ans=ans*10+ch-'0',ch=gc();    ans*=f;return 1;}template
         
          int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF;}template
          
           int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;}typedef long long ll;const int Maxn=1100;const int inf=0x3f3f3f3f;int n,m,mp[Maxn][Maxn],l[Maxn][Maxn],h[Maxn][Maxn],b[Maxn],num[Maxn],num2[Maxn];int main() {// freopen("test.in","r",stdin); read(n,m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(mp[i][j]); for(int i=1;i<=n;i++) { map
           
             ma; for(int j=1;j<=m;j++) b[j]=mp[i][j]; sort(b+1,b+m+1); for(int j=1;j<=m;j++) if(!ma[b[j]]) ma[b[j]]=++num[i]; for(int j=1;j<=m;j++) h[i][j]=ma[mp[i][j]]; } for(int i=1;i<=m;i++) { map
            
              ma; for(int j=1;j<=n;j++) b[j]=mp[j][i]; sort(b+1,b+n+1); for(int j=1;j<=n;j++) if(!ma[b[j]]) ma[b[j]]=++num2[i]; for(int j=1;j<=n;j++) l[j][i]=ma[mp[j][i]]; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) printf("%d ",max(l[i][j],h[i][j])+max(num[i]-h[i][j],num2[j]-l[i][j])); putchar('\n'); } return 0;}

B - Camp Schedule

首先用kmp求出next[n]，然后先弄出来一个串，然后每次从next[n]一直到最后，如果有一种用完了就不弄了。

#include
    
     #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vi vector
     
      #define vit vector
      
       ::iterator#define pir pair
       
        #define fr first#define sc second#define mp(x,y) make_pair(x,y)using namespace std;inline char gc() {//  static char buf[100000],*p1,*p2;//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;    return getchar();}template
        
         int read(T &ans) {    ans=0;char ch=gc();T f=1;    while(!isdigit(ch)) {        if(ch==EOF) return -1;        if(ch=='-') f=-1;        ch=gc();    }    while(isdigit(ch))        ans=ans*10+ch-'0',ch=gc();    ans*=f;return 1;}template
         
          int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF;}template
          
           int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;}typedef long long ll;const int Maxn=1100000;const int inf=0x3f3f3f3f;int nxt[Maxn],bj[3];char s[Maxn],t[Maxn];void find_next(char *a) { nxt[0]=0; int len=strlen(a); int temp=0; for(int i=1;i
           
            0&&a[temp]!=a[i])temp=nxt[temp]; if(a[temp]==a[i]) nxt[i+1]=++temp; else nxt[i+1]=0; }}int print() { while(bj[0]--) putchar('0'); while(bj[1]--) putchar('1'); putchar('\n'); return 0;}int main() {// freopen("test.in","r",stdin); scanf("%s",s); scanf("%s",t); find_next(t); int ls=strlen(s),lt=strlen(t); for(int i=0;i

C - Museums Tour

首先构造分层图，新的点可以用二元组\((i,j)\)来表示第\(i\)天位于\(j\)号点的状态，对于原图上的一条边，直接连接对应点的每一天即可，然后跑强连通分量，对于每个强连通分量记录一下总共会经过多少个不同的博物馆，然后就可以DP了。

#include
    
     #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vi vector
     
      #define vit vector
      
       ::iterator#define pir pair
       
        #define fr first#define sc second#define mp(x,y) make_pair(x,y)using namespace std;inline char gc() {//  static char buf[100000],*p1,*p2;//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;    return getchar();}template
        
         int read(T &ans) {    ans=0;char ch=gc();T f=1;    while(!isdigit(ch)) {        if(ch==EOF) return -1;        if(ch=='-') f=-1;        ch=gc();    }    while(isdigit(ch))        ans=ans*10+ch-'0',ch=gc();    ans*=f;return 1;}template
         
          int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF;}template
          
           int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;}typedef long long ll;const int Maxn=5100000;const int inf=0x3f3f3f3f;int to[Maxn],nxt[Maxn],first[Maxn],tot=1;int du[Maxn],belong[Maxn],flag[Maxn],bj[Maxn],f[Maxn];int n,m,d,u,v,num,dp[Maxn];queue
           
             q;inline void add(int u,int v) { to[tot]=v; nxt[tot]=first[u]; first[u]=tot++; du[v]++;}struct graph { int to[Maxn],nxt[Maxn],first[Maxn],tot; int s[Maxn],ran[Maxn],cnt,vis[Maxn],bj[Maxn],top; inline void add(int u,int v) { to[tot]=v; nxt[tot]=first[u]; first[u]=tot++; } int dfs(int root) { vis[root]=1,bj[root]=1; s[++top]=root; ran[root]=++cnt; int low=cnt; for(int i=first[root];i;i=nxt[i]) if(!vis[to[i]]) qmin(low,dfs(to[i])); else if(bj[to[i]]) qmin(low,ran[to[i]]); if(low==ran[root]) { num++; int temp=top; do { int sxz=s[top]; belong[sxz]=num; bj[sxz]=0; if(::bj[sxz]&&!flag[(sxz-1)/d]) f[num]++,flag[(sxz-1)/d]=1; } while(s[top--]!=root); for(int i=top+1;i<=temp;i++) flag[(s[i]-1)/d]=0; } return low; } void tarjan() { for(int i=1;i<=n*d;i++) if(!vis[i]) dfs(i); for(int i=1;i<=n*d;i++) for(int j=first[i];j;j=nxt[j]) if(belong[i]!=belong[to[j]]) ::add(belong[to[j]],belong[i]); }}t1;void topo() { for(int i=1;i<=num;i++) if(!du[i]) q.push(i),dp[i]=f[i]; while(!q.empty()) { int now=q.front();q.pop(); for(int i=first[now];i;i=nxt[i]) { qmax(dp[to[i]],dp[now]); if(!--du[to[i]]) { dp[to[i]]+=f[to[i]]; q.push(to[i]); } } }}int main() {// freopen("test.in","r",stdin); read(n,m,d); t1.tot=1; for(int i=1;i<=m;i++) { read(u,v); u--,v--; u*=d,v*=d; for(int j=1;j

D - Cooperative Game

首先让两个点开始跑，每次一个跑一步，另一个跑两步，那么他们相遇时，跑一步的很显然没有超过一圈，设为\(t+x\)步，那么另一个跑了\(2*(t+x)\)步。

由于第二个人多跑的一定是一些整圈，所以\(c|(t+x)\)，这两个人都在圈上的第\(x\)个位置，那么如果再让他们都跑\(t\)步，最终一定是都在终点了。

#include
    
     #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vi vector
     
      #define vit vector
      
       ::iterator#define pir pair
       
        #define fr first#define sc second#define mp(x,y) make_pair(x,y)using namespace std;inline char gc() {//  static char buf[100000],*p1,*p2;//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;    return getchar();}template
        
         int read(T &ans) {    ans=0;char ch=gc();T f=1;    while(!isdigit(ch)) {        if(ch==EOF) return -1;        if(ch=='-') f=-1;        ch=gc();    }    while(isdigit(ch))        ans=ans*10+ch-'0',ch=gc();    ans*=f;return 1;}template
         
          int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF;}template
          
           int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;}typedef long long ll;const int Maxn=1100000;const int inf=0x3f3f3f3f;char s[110];int getnum() { int x; read(x); gets(s); return x;}int main() {// freopen("test.in","r",stdin); do { printf("next 0 1\n"); fflush(stdout); getnum(); printf("next 0\n"); fflush(stdout); } while(getnum()>2); do { printf("next 0 1 2 3 4 5 6 7 8 9\n"); fflush(stdout); } while(getnum()>1); printf("done\n"); fflush(stdout); return 0;}

E - Train Car Selection

答案一定是在一个凸壳上的，那么从前面插入一个点时，就重置一下，凸壳上只有一个点\((0,0)\)，等差数列公差\(a\)和首项\(b\)也置为0。

从后面插入时要插入\((n,-(an+b))\)，然后维护凸壳即可。

#include
    
     #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vi vector
     
      #define vit vector
      
       ::iterator#define pir pair
       
        #define fr first#define sc second#define mp(x,y) make_pair(x,y)using namespace std;inline char gc() {//  static char buf[100000],*p1,*p2;//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;    return getchar();}template
        
         int read(T &ans) {    ans=0;char ch=gc();T f=1;    while(!isdigit(ch)) {        if(ch==EOF) return -1;        if(ch=='-') f=-1;        ch=gc();    }    while(isdigit(ch))        ans=ans*10+ch-'0',ch=gc();    ans*=f;return 1;}template
         
          int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF;}template
          
           int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;}typedef long long ll;const int Maxn=1100000;const int inf=0x3f3f3f3f;int m,opt;ll a,b,n,x;pair
           
             p[Maxn];ll calc(pair
            
              x) { return a*x.fr+x.sc+b;}int main() {// freopen("test.in","r",stdin); read(n,m); int l=1,r=1; p[1]=mp(0,0); while(m--) { read(opt); if(opt==1) { l=r=1; p[1]=mp(0,0); read(x); a=b=0; n+=x; } else if(opt==2) { pair
             
               now=mp(n,-(n*a+b)); while(r>l&&(long double)(now.sc-p[r].sc)*(p[r].fr-p[r-1].fr)<(long double)(p[r].sc-p[r-1].sc)*(now.fr-p[r].fr)) r--; p[++r]=now; read(x); n+=x; } else if(opt==3) { read(x);b+=x; read(x);a+=x; } while(r>l&&calc(p[r])>=calc(p[r-1])) r--; printf("%lld %lld\n",p[r].fr+1,calc(p[r])); } return 0;}

转载于:https://www.cnblogs.com/shanxieng/p/10499304.html

你可能感兴趣的文章