AtCoder Beginner Contest 285（A~E）

A - Edge Checker 2

在满二叉树中，判断两个两个点是否是父子关系

void solve()
{
    int a,b;
    cin>>a>>b;
    if(b==2*a || b==2*a+1) puts("Yes");
    else puts("No");
}

B - Longest Uncommon Prefix

模拟，当s[i] == s[i+k]时或者i+k>=字符串长度时,得到答案

void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int len = s.length();
    for(int i=1;i<=n-1;i++){
        for(int j=0;j<len;j++){
            if(j+i<n){
                if(s[j]==s[j+i]){
                    cout<<j<<endl;
                    break;
                }
            }
            if(j+i>=n){
                cout<<j<<endl;
                break;
            }
        }
    }
}

C - abc285_brutmhyhiizp

相当于26进制转换，从高位开始计算

void solve()
{
    string s;
    cin>>s;
    int order = 0;
    int len = s.length();
    for(int i=0;i<len;i++){
        order += (LL)pow(26,len-i-1)*(s[i]-'A'+1);
    }
    cout<<order<<endl;
}

D - Change Usernames

根据给出的点建立有向图，有向图里没有环时符合题目条件，用dfs搜索一遍有向图即可判断出是否有负环。  

题目给出的顶点是字符串，需要开一个map来将字符串映射到某个整型的值，再进行建图。

const int N = 200000+10;
int n;
string s[N],t[N];
map<string,int>mp;
vector<int>G[N];
int vis[N];
bool ans;
 
void dfs(int u)
{
    if(vis[u]) return ;
    vis[u] = 1;
    int size = G[u].size();
    for(int i=0;i<size;i++){
        int temp = G[u][i];
        if(vis[temp]==1) ans = true;
        else if(vis[temp]!=2) dfs(temp);
    } 
    vis[u] = 2;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i]>>t[i];
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(!mp[s[i]]) mp[s[i]] = ++cnt;
        if(!mp[t[i]]) mp[t[i]] = ++cnt;
    }
    for(int i=1;i<=n;i++) G[mp[s[i]]].push_back(mp[t[i]]);
    for(int i=1;i<=n;i++) dfs(mp[s[i]]);
    if(ans) puts("No");
    else puts("Yes");
}

E - Work or Rest

假设两个假期之间间隔d天，

当d=0,时，区间生产力之和是0;  

d=1时为a[1]  

d=2时为2*a[1]  

d=3时为2*a[1]+a[2]

以此类推

推出假期间隔之间的生产力之和为a[(i+1)/2](i从1到d)之和  

f[i][j]为确定了i天，且已经连续工作了j天，集合性质为生产力之和的最大值

朴素状态转移方程：  

f[i+1][j+1] = max(f[i+1][j+1],f[i][j])  

f[i+1][0] = max(f[i+1][0],f[i][j]+g[j])

优化成一维后状态转移方程：

f[i]=max(f[i],f[j]+g[i-j-1])

const int N = 5000+10;
int n;
ll a[N];
ll g[N];//前缀和数组
ll f[N];

void solve()
{
    cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	g[0]=0; 
    for(int i=1;i<=n;i++) g[i]=g[i-1]+a[(i+1)/2];
	f[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n-1;j++){
            f[i]=max(f[i],f[j]+g[i-j-1]);
        }
    }
	cout<<f[n];
}