首页 > 其他 > 详细

codeforces-1131 (div2)

时间：2019-04-17 20:40:15      阅读：102      评论：0      收藏：0      [点我收藏+]

A.把右上角的凹缺口补上变成凸的就成了规则矩形

技术分享图片 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<‘0‘ || c>‘9‘){if (c == ‘-‘) f = -1;c = getchar();}
while (c >= ‘0‘&&c <= ‘9‘){x = x * 10 + c - ‘0‘;c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
int main(){
    LL w1,h1,w2,h2;
    scanf("%lld%lld%lld%lld",&w1,&h1,&w2,&h2);
    LL ans = w1 + w1 + h1 + h1 + h2 + h2 + 4;
    Prl(ans);
    return 0;
}
A

 

B.画在图上就是两条斜线之间有多少可以水平的线，显然是下面这条线的最高点和上面这条线的最低点作差，记得打一个vis标记记录哪些线取过了

技术分享图片 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<‘0‘ || c>‘9‘){if (c == ‘-‘) f = -1;c = getchar();}
while (c >= ‘0‘&&c <= ‘9‘){x = x * 10 + c - ‘0‘;c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
int main(){
    Sca(N);
    LL la = 0,lb = 0;
    LL ans = 1;
    LL now = 1;
    for(int i = 1; i <= N ; i ++){
        LL a,b; scanf("%lld%lld",&a,&b);
        int t = max(max(la,lb),now);
        if(min(a,b) >= t){
            ans += min(a,b) - t + 1;
            now = min(a,b) + 1;
        }
        la = a; lb = b;
    }
    Prl(ans);
    return 0;
}
B

 

C.开始觉得要二分，后来觉得要O(n3),仔细一看发现O(n)

显然取两条非递减的线，从最高点往两边降低，贪心的发现每次都升高最高点更低的那个路径就可以了。

技术分享图片 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<‘0‘ || c>‘9‘){if (c == ‘-‘) f = -1;c = getchar();}
while (c >= ‘0‘&&c <= ‘9‘){x = x * 10 + c - ‘0‘;c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
int a[maxn];
int b[maxn],c[maxn];
int main(){
    Sca(N);
    for(int i = 1; i <= N ; i ++) Sca(a[i]);
    sort(a + 1,a + 1 + N);
    int cnt1 = 0,cnt2 = 0;
    b[++cnt1] = a[1];
    c[++cnt2] = a[2];
    for(int i = 3; i <= N ; i ++){
        if(b[cnt1] < c[cnt2]) b[++cnt1] = a[i];
        else c[++cnt2] = a[i];
    }
    for(int i = 1; i <= cnt1; i ++) printf("%d ",b[i]);
    for(int i = cnt2; i >= 1; i --) printf("%d ",c[i]);
    return 0;
}
C

 

D.拓扑排序例题。

先把所有的等于号用并查集合并，找大小之间的冲突。然后用拓扑排序标记顺便判环。

技术分享图片 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<‘0‘ || c>‘9‘){if (c == ‘-‘) f = -1;c = getchar();}
while (c >= ‘0‘&&c <= ‘9‘){x = x * 10 + c - ‘0‘;c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 2010;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
char MAP[maxn][maxn];
struct Edge{
    int to,next;
}edge[maxn * maxn * 2];
int fa[maxn * 2],tot,head[maxn * 2],ind[maxn * 2];
void init(){
    for(int i = 0 ; i <= N + M; i ++){
        head[i] = -1;
        fa[i] = i;
        ind[i] = 0;
    } 
    tot = 0;
}
void add(int u,int v){
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void Union(int a,int b){
    a = find(a); b = find(b);
    fa[a] = b;
}
int ans[maxn];
int main(){
    Sca2(N,M); init();
    bool flag = 1;
    for(int i = 1; i <= N ; i ++){
        scanf("%s",MAP[i] + 1);
        for(int j = 1; j <= M ; j ++){
            if(MAP[i][j] == ‘=‘){
                Union(i,j + N);
            }
        }
    }
    for(int i = 1; i <= N && flag; i ++){
        for(int j = 1; j <= M ; j ++){
            if(MAP[i][j] == ‘=‘) continue;
            int a = find(i),b = find(j + N);
            if(a == b){
                flag = 0;
                break;
            }
            if(MAP[i][j] == ‘>‘){
                add(b,a); ind[a]++;
            }else{
                add(a,b); ind[b]++;
            }
        }
    }
    if(!flag){
        puts("No");
        return 0;
    }
    queue<int>Q;
    for(int i = 1; i <= N + M; i ++){
        if(find(i) == i && !ind[i]){
            ans[i] = 1;
            Q.push(i);
        } 
    }
    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        for(int i = head[u]; ~i; i = edge[i].next){
            int v = edge[i].to;
            ans[v] = max(ans[v],ans[u] + 1);
            ind[v]--;
            if(!ind[v]) Q.push(v);
        }
    }
    for(int i = 1; i <= N + M; i ++){
        if(fa[i] == i && ind[i]) flag = 0;
    }
    if(!flag){
        puts("No");
        return 0;
    }
    puts("Yes");
    for(int i = 1; i <= N ; i ++){
        printf("%d ",ans[find(i)]);
    }
    puts("");
    for(int j = N + 1; j <= N + M; j ++){
        printf("%d ",ans[find(j)]);
    }
    return 0;
}
D

 

E.dp[100000][30]记录到i这个字符串j的最长长度。

如果右边的字符串都为k，那么dp[i][j] = max(dp[i][j],len * (dp[i - 1][j] + 1) + dp[i - 1][j]);

否则字符就变为前后缀与他相同的最长长度相加

如果曾经出现过这个字符，这个字符的出现次数至少为1

技术分享图片 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<‘0‘ || c>‘9‘){if (c == ‘-‘) f = -1;c = getchar();}
while (c >= ‘0‘&&c <= ‘9‘){x = x * 10 + c - ‘0‘;c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
LL ans[40];
LL dp[maxn][30];
LL pre[100000];
LL tmp[30];
char str[100000];
int main(){
    Sca(N);
    for(int i = 1; i <= N ; i ++){
        scanf("%s",str);
        LL len = strlen(str);
        LL a = 1,b = len;
        for(int j = 0 ; j < 26; j ++) tmp[j] = 0;
        for(int j = 0; j < len; j ++){
            if(j && str[j - 1] == str[j]) pre[j] = pre[j - 1] + 1;
            else pre[j] = 1;
            tmp[str[j] - ‘a‘] = max(tmp[str[j] - ‘a‘],pre[j]);
        }
        for(int j = 0 ; j < 26; j ++){
            dp[i][j] = tmp[j];
            int l = 0,r = len - 1;
            while(l <= r && str[l] == j + ‘a‘) l++;
            while(r > l && j + ‘a‘ == str[r]) r--;
            if(l == len){
                dp[i][j] = max(dp[i][j],len * (dp[i - 1][j] + 1) + dp[i - 1][j]);    
            }else if(dp[i - 1][j]){
                dp[i][j] = max(dp[i][j],l + len - r);
            }
        } 
    }
    LL sum = 0;
    for(int j = 0 ; j < 26; j ++) sum = max(sum,dp[N][j]);
    Prl(sum);
    return 0;
}
E

 

codeforces-1131 (div2)

原文：https://www.cnblogs.com/Hugh-Locke/p/10725924.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！