首页 > 代码库 > Codeforces Round #384 (Div. 2) //复习状压... 罚时爆炸 BOOM

Codeforces Round #384 (Div. 2) //复习状压... 罚时爆炸 BOOM

2024-08-27 08:09:10   219人阅读

不想欠题了..... 多打打CF才知道自己智商不足啊...

A. Vladik and flights

给你一个01串  相同之间随便飞 没有费用 不同的飞需要费用为  abs i-j   

真是题意杀啊，，，实际上我们只考虑01转换的代价一定为1如果目的地和起点相同  费用为0 

不相同  肯定为1  因为0旁边必然有1

技术分享 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string.h>
#include <cctype>
#include <climits>
using namespace std;
typedef long long ll;
template <class T>
inline bool r(T &ret) 
{
    char c; 
    int sgn;
    if (c = getchar(), c == EOF) 
    {
        return 0; //EOF 
    }
    while (c != ‘-‘ && (c < ‘0‘ || c > ‘9‘)) 
    {
        c = getchar(); 
    }
    sgn = (c == ‘-‘) ? -1 : 1;
    ret = (c == ‘-‘) ? 0 : (c - ‘0‘); 
    while (c = getchar(), c >= ‘0‘ && c <= ‘9‘) 
    {
        ret = ret * 10 + (c - ‘0‘); 
    }
    ret *= sgn;
    return 1;
}
const int N = 1e5+10;
char ch[N];
int main()
{
    int n;
    r(n);
    int x,y;
    r(x),r(y);
    scanf("%s",ch+1);
    if(ch[x]==ch[y])
    {
        printf("0\n");
    }
    else{
        printf("1\n");
    }
    return 0;
}
zz

B. Chloe and the sequence

给一个n，然后按照 1  121 1213121 的第n个串

那么肯定是二分n次必得....  赛场拿python写的   （L+R）没加括号T1

技术分享 
n,k = map(int, input().split())
def calc(k):
    L = 0
    R = 2**n
    M = L+R//2
    ans = 0
    while(k!=M):
        if(k>M):
            L = M
        else:
            R = M
        M = (L+R)//2
        ans+=1
    print(n-ans)
calc(k)
Py

C. Vladik and fractions

问2/n能不能由1/a+1/b+1/c（a,b,c互不相同） 太粗心，没看到互不相同 wa1 没特判1 被hack 1

手推 a = n b = n+1 c = n*(n+1)

n=1分不出的

技术分享 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string.h>
#include <cctype>
#include <climits>
using namespace std;
typedef long long ll;
template <class T>
inline bool r(T &ret) 
{
    char c; 
    int sgn;
    if (c = getchar(), c == EOF) 
    {
        return 0; //EOF 
    }
    while (c != ‘-‘ && (c < ‘0‘ || c > ‘9‘)) 
    {
        c = getchar(); 
    }
    sgn = (c == ‘-‘) ? -1 : 1;
    ret = (c == ‘-‘) ? 0 : (c - ‘0‘); 
    while (c = getchar(), c >= ‘0‘ && c <= ‘9‘) 
    {
        ret = ret * 10 + (c - ‘0‘); 
    }
    ret *= sgn;
    return 1;
}

int main()
{
    int n;
    r(n);
    if(n==1) printf("-1");
    else printf("%d %d %d\n",n,n+1,n*(n+1));
    return 0;
}
AC

 

D.Chloe and pleasant prizes

MK 一下

 
 

 

E. Vladik and cards

题意给以一个1-8组成的串  选出一个子串（在原串中可以不连续）  选出来的串 每个数相同的一定相邻  而且 每种数的个数相差不超过1

比赛时只想到DFS的解，后来证实是错的

后来看别人的代码一脸蒙=。=... 后来一神说了两个数组的作用才明白...就这样   参考claris的写法

而且....

这样也写了好久  而且还少更新状态   长度可以为0...... 

技术分享 
#include<cstdio>
#include<cstring>
void Min(int &a,int b) {if(a>b) a=b;}
void Max(int &a,int b) {if(a<b) a=b;}
const int maxn = 1010;
int cnt[10];
int g[maxn][maxn][10];//i j k 
int dp[256][10];//i 选择方案  j 代表  长度的集合个数   长度最多n/8+1 
int val[maxn];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]),val[i]--;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n+5;j++)
            for(int k=0;k<=8;k++) g[i][j][k] = maxn;
        memset(cnt,0,sizeof(cnt));
        for(int j=i;j<=n;j++)
            g[i][++cnt[val[j]]][val[j]] = j; 
    }
    int ans = 0;
    for(int i=0;i*8<=n;i++)//长度 
    {
        for(int j=0;j<256;j++)
            for(int k=0;k<=8;k++)
                dp[j][k] = maxn;
        dp[0][0] = 1; //从1开始 
        for(int j=0;j<256;j++)//选择方案 
        {
            for(int k=0;k<=8;k++)// 
            {
                if(dp[j][k]>n)continue; 
                for(int l=0;l<8;l++)
                {
                    if((1<<l)&j) continue;
                    Min(dp[j|(1<<l)][k],g[dp[j][k]][i][l]+1);
                    Min(dp[j|(1<<l)][k+1],g[dp[j][k]][i+1][l]+1);
                }
            }
        }
        for(int j=0;j<=8;j++) if(dp[255][j]<n+2){
            Max(ans,j+8*i);
        }
    }
    printf("%d\n",ans);
    return 0;
}
状压DP

 

Codeforces Round #384 (Div. 2) //复习状压... 罚时爆炸 BOOM


联系
我们