2016 Multi-University Training Contest 4(部分) - dblank

2016 Multi-University Training Contest 4(部分)

<h2>1001 Another Meaning</h2>
首先kmp打一个表,vis[i]表示以i结尾的子串是b串,然后dp[i]表示到第i个字符的意思数,对于vis[i]=0, dp[i] = dp[i-1], 对于vis[i] = 1, dp[i] = dp[i-1] + dp[i -len2]。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
using namespace std;

typedef long long ll;
const int N = 200010;
const int MOD = 1000000007;
char s[N], s1[N];
int nt[N];
int vis[N];
int dp[N];
void getnt(char s[])
{
    int i = 0, j = -1;
    nt[0] = -1;
    while(s[i])
    {
        if(j == -1 || s[i] == s[j])
        {
            i++, j++;
            if(s[i] != s[j]) nt[i] = j;
            else nt[i] = nt[j];
        }
        else j = nt[j];
    }
}

void kmp(char s1[], char s2[])
{
    getnt(s2);
    int i = 0, j = 0;
    while(s1[i])
    {
        if(j == -1 || s1[i] == s2[j])
            i++, j++;
        else j = nt[j];
        if(j != -1 && !s2[j])
        {
            vis[i] = 1;
            j = nt[j];
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    int cas = 1;
    while(t--)
    {
        scanf("%s%s", s, s1);
        int len1 = strlen(s), len2 = strlen(s1);
        memset(vis, 0, sizeof vis);
        kmp(s, s1);
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(int i = 1; i<=len1; i++)
        {
            if(!vis[i])
                dp[i] = dp[i-1];
            else
            {
                dp[i] = (dp[i-1] + dp[i-len2])%MOD;
                //printf("%d %dn", dp[i], dp[i-1] + dp[i-len2]);
            }
        }
        printf("Case #%d: %dn",cas++, dp[len1]);
    }
    return 0;
}

<h2>1010  The All-purpose Zero</h2>
最后的结果肯定是所有的0都用上了,先把0拿出来,做lis,为了保证严格递增,剩下的数要减去前面0的个数。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000+ 10, Mod = 1000000000;
typedef long long ll;
int n, a[N], b[N], c[N];
int main()
{
    int t;
    cin>>t;
    for(int cas = 1; cas<=t; cas++)
    {
        int n;
        scanf("%d", &n);
        int cnt = 1, zero = 0;
        for(int i = 1; i<=n; i++)
        {
            scanf("%d", &a[i]);
            if(a[i] == 0)
                zero++;
            else
                c[cnt++] = a[i] - zero;
        }
        int len = 0;
        b[0] = -1;
        for(int i = 1; i<cnt; i++)
        {
            int pos = lower_bound(b, b+len, c[i]) - b;
            b[pos] = c[i];
            if(pos == len)
            len++;
        }
        printf("Case #%d: %dn", cas, zero+len);
    }
    return 0;
}

<h2>1011 Where Amazing Happens</h2>
直接。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
using namespace std;

int main()
{
    map<string, int> mpa;
    mpa["Cleveland Cavaliers"]++;
    mpa["Golden State Warriors"]++;
    mpa["San Antonio Spurs"]++;
    mpa["Miami Heat"]++;
    mpa["Miami Heat"]++;
    mpa["Dallas Mavericks"]++;
    mpa["L.A. Lakers"]++;
    mpa["L.A. Lakers"]++;
    mpa["Boston Celtics"]++;
    mpa["San Antonio Spurs"]++;
    mpa["Miami Heat"]++;
    mpa["San Antonio Spurs"]++;
    mpa["Detroit Pistons"]++;
    mpa["San Antonio Spurs"]++;
    mpa["L.A. Lakers"]++;
    mpa["L.A. Lakers"]++;
    mpa["L.A. Lakers"]++;
    mpa["San Antonio Spurs"]++;
    mpa["Chicago Bulls"]++;
    mpa["Chicago Bulls"]++;
    mpa["Chicago Bulls"]++;
    mpa["Houston Rockets"]++;
    mpa["Houston Rockets"]++;
    mpa["Chicago Bulls"]++;
    mpa["Chicago Bulls"]++;
    mpa["Chicago Bulls"]++;
    mpa["Detroit Pistons"]++;
    mpa["Detroit Pistons"]++;
    mpa["L.A. Lakers"]++;
    mpa["L.A. Lakers"]++;
    mpa["Boston Celtics"]++;
    mpa["L.A. Lakers"]++;
    mpa["Boston Celtics"]++;
    mpa["Philadelphia 76ers"]++;
    mpa["L.A. Lakers"]++;
    mpa["Boston Celtics"]++;
    mpa["L.A. Lakers"]++;
    mpa["Seattle Sonics"]++;
    mpa["Washington Bullets"]++;
    mpa["Portland Trail Blazers"]++;
    mpa["Boston Celtics"]++;
    mpa["Golden State Warriors"]++;
    mpa["Boston Celtics"]++;
    mpa["New York Knicks"]++;
    mpa["L.A. Lakers"]++;
    mpa["Milwaukee Bucks"]++;
    mpa["New York Knicks"]++;
    mpa["Boston Celtics"]++;
    mpa["Boston Celtics"]++;
    mpa["Philadelphia 76ers"]++;
    mpa["Boston Celtics"]++;
    mpa["Boston Celtics"]++;
    mpa["Boston Celtics"]++;
    mpa["Boston Celtics"]++;
    mpa["Boston Celtics"]++;
    mpa["Boston Celtics"]++;
    mpa["Boston Celtics"]++;
    mpa["Boston Celtics"]++;
    mpa["St. Louis Hawks"]++;
    mpa["Boston Celtics"]++;
    mpa["Philadelphia Warriors"]++;
    mpa["Syracuse Nats"]++;
    mpa["Minneapolis Lakers"]++;
    mpa["Minneapolis Lakers"]++;
    mpa["Minneapolis Lakers"]++;
    mpa["Rochester Royals"]++;
    mpa["Minneapolis Lakers"]++;
    mpa["Minneapolis Lakers"]++;
    mpa["Baltimore Bullets"]++;
    mpa["Philadelphia Warriors"]++;

    int t, cas = 0;
    char s[100];
    scanf("%d", &t);
    getchar();
    while(t--)
    {
        gets(s);
        printf("Case #%d: %dn", ++cas, mpa[s]);
    }
    return 0;
}

<h2>1012 Bubble Sort</h2>
其实答案就是左边比它大的和右边比它小的最大值,直接变查询边更新树状数组就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000+ 10, Mod = 1000000000;
typedef long long ll;
int c[N], n, ans[N], a[N];
int lowbit(int x)
{
    return x &(-x);
}
int sum(int x)
{
    int res = 0;
    while(x>=1)
    {
        res += a[x];
        x -= lowbit(x);
    }
    return res;
}
void update(int x)
{
    while(x<=n)
    {
        a[x]++;
        x += lowbit(x);
    }
}
int main()
{
    int t;
    cin>>t;
    for(int cas = 1; cas<=t; cas++)
    {
        scanf("%d", &n);
        memset(a, 0, sizeof(a));
        for(int i = 1; i<=n; i++)
        {
            scanf("%d", &c[i]);
            int y =i -1- sum(c[i]-1);
            ans[c[i]] = max(c[i]-i+y, y);
            update(c[i]);
        }
        printf("Case #%d:",cas);
        for(int i = 1; i<=n; i++)
            printf(" %d", ans[i]);
        printf("n");
    }
    return 0;
}

 

相关文章

发表新评论