Educational Codeforces Round 18 C dp,思维 D lowbit,思维

题意：给出一个字符串，只包含数字，要求：删去尽可能少的数字，使留下的数能被3整除，且不含前导零。

tags：可以dp做，也可以分类讨论，但分类讨论的大半都被叉了。。so，还是dp大法好

从左往右，用dp[i][j]表示前i个数字中，可使数字和%3==j的最大数字个数。

状态转移：如果取第 i 个数字，dp[i][j]=dp[i-1][(j-s[i]+9)%3]+1 ; 如果删除掉第 i 个数字，dp[i][j]=dp[i-1][j]。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 200005;

char s[N], ans[N];
int n, dp[N][3];    //dp[i][j]表示前i个数字中，可使数字和%3==0的最大数字个数 
int main()
{
    mes(dp, -1);
    scanf("%s", s+1);  n=strlen(s+1);
    rep(i,1,n) s[i]=s[i]-'0';
    dp[1][s[1]%3]=1;
    rep(i,2,n)         //dp转移 
    {
        if(s[i]) dp[i][s[i]%3]=1;
        rep(j,0,2) if(dp[i-1][(j-s[i]+9)%3]!=-1)
            dp[i][j]=dp[i-1][(j-s[i]+9)%3]+1;
        rep(j,0,2) dp[i][j]=max(dp[i][j], dp[i-1][j]);
    }
    
    if(dp[n][0]==-1)     //不可能通过删除0~2个数字的情况 
    {
        rep(i,1,n) if(s[i]%3==0) return 0*printf("0
");
        return 0*printf("-1
");
    }
    else 
    {
        int len=0, j=0;
        per(i,n,1) if(dp[i-1][j]<dp[i][j])     
            ans[++len]=s[i]+'0', j=(j-s[i]+9)%3;    // j找前驱 
        per(i,len,1) putchar(ans[i]);
    }

    return 0;
}

View Code

D. Paths in a Complete Binary Tree

题意：一棵含n个结点的完整的二叉树，q个询问。二叉树中的结点按中序遍历标号为1~n，也就是一棵二叉排序树。每次询问有一个数ui和一个字符串si，表示从ui结点出发，按si 的指令行走，问最后到达哪个结点。

tags：真的ZZ，比赛的时候就是想不出来

只要稍微往lowbit的方向想一想就明白了。然后在向上时要判断左右有点难搞，可以标出几个点的数据，多看看就能发现规律了。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 200005;

ll n, q, ui;
char s[N];
int main()
{
    scanf("%lld %lld", &n, &q);
    while(q--) {
        scanf("%lld %s", &ui, s);
        for(int i=0; s[i]; i++) {
            ll x=(ui&-ui);
            if(s[i]=='R') ui+= x/2;
            if(s[i]=='L') ui-= x/2;
            if(s[i]=='U' && ui!=(n+1)/2) {
                if((ui/(x*2))&1) ui-=x;
                else ui+=x;
            }
        }
        printf("%lld
", ui);
    }

    return 0;
}

View Code