Codeforces Round #305 (Div. 1) problem: (B) Mike and Feet

#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct node{
    int a,l,r;
};
node arr[200005];

bool compare (node x, node y){
    return x.a > y.a;
}

int n;
stack<int> s;

int main(){
    scanf("%d",&n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i].a);

    //left
    for (int i = 0; i < n; ++i)
    {
        if(s.empty())
            s.push(i);
        else{
            int top = s.top();
            if(arr[top].a <= arr[i].a)
                s.push(i);
            else{
                while(arr[top].a > arr[i].a){
                    arr[top].r = i;
                    s.pop();
                    if(s.empty())
                        break;
                    top  = s.top();
                }
                s.push(i);
            }
        }
    }
    while(!s.empty()){
        int top = s.top();
        arr[top].r = n;
        s.pop();
    }

    //left
    for (int i = n-1; i >=0 ; --i)
    {
        if(s.empty())
            s.push(i);
        else{
            int top = s.top();
            if(arr[top].a <= arr[i].a)
                s.push(i);
            else{
                while(arr[top].a > arr[i].a){
                    arr[top].l = i;
                    s.pop();
                    if(s.empty())
                        break;
                    top  = s.top();
                }
                s.push(i);
            }
        }
    }
    while(!s.empty()){
        int top = s.top();
        arr[top].l = -1;
        s.pop();
    }

    for (int i = 0; i < n; ++i)
    {
        arr[i].r -= (i+1);
        arr[i].l = i - arr[i].l - 1;
    }

    //find ans
    sort(arr, arr+n, compare);
    int now = 0;
    for (int x = 1; x <= n; ++x)
    {
        while(arr[now].l + arr[now].r + 1 < x){
            now++;
        }  
        printf("%d ", arr[now].a);
    }
    printf("\n");

}

TIOJ 1489 E.核心字串

#include <cstdio>
#include <cstdlib>
#include <string.h>
using namespace std;

char a[1000005], ans[1000005];
int cnt[26];
int ans_st;
int ans_l;

bool check(){
    for (int i = 0; i < 26; ++i)
        if(cnt[i] == 0)
            return false;
    return true;
}

void update(int st, int len){
    if(len < ans_l){
        ans_st = st;
        ans_l = len;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    while(n > 0){
        scanf("%s", a);
        
        memset(cnt, 0, sizeof(cnt));

        ans_l = 1e9;
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i)
        {
            r = i;
            cnt[a[i] - 'a']++;

            if(!check())
                continue;

            while(1){
                update(l, r - l + 1);
                l++;
                if(--cnt[a[l - 1] - 'a'] == 0)
                    break;
            }
        }

        if(ans_l != 1e9){
            ans[ans_l] = '\0';
            strncpy(ans, a + ans_st, ans_l);
        }

        printf("%s\n", ans_l != 1e9 ? ans:"not found");

        scanf("%d", &n);
    }  
} 

TIOJ 1196 小豬Piggy

#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
using namespace std;
char s[15][15];
int dp[15][15];

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%s", s[i]);

    memset(dp, -1, sizeof(dp));

    dp[0][0] = 0;
    for (int i = 1; i < n; ++i){
        if(dp[i - 1][0] >= 0 && s[i][0] != 'X')
            dp[i][0] = dp[i - 1][0] + s[i][0] - '0';

        if(dp[0][i - 1] >= 0 && s[0][i] != 'X')
            dp[0][i] = dp[0][i - 1] + s[0][i] - '0';
    }

    for (int i = 1; i < n; ++i)
    for (int j = 1; j < n; ++j){
        if(s[i][j] == 'X')
            continue;

        if(dp[i - 1][j] < 0){
            if(dp[i][j - 1] < 0)
                continue;
            dp[i][j] = dp[i][j - 1] + s[i][j] - '0';
        }
        else if(dp[i][j - 1] < 0)
            dp[i][j] = dp[i - 1][j] + s[i][j] - '0';
        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + s[i][j] - '0';
    }

    if(dp[n - 1][n - 1] == -1)
        printf("X\n");
    else
        printf("%d\n", dp[n - 1][n - 1] - 'B' + '0');
}

TIOJ 1291 G.N 箱M 球

#include <cstdio>
#include <cstdlib>
#include <string.h>
#define modu (int)1e6
using namespace std;
int dp[201][201];

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    memset(dp, 0, sizeof(dp));

    dp[0][0] = 1;
    for (int i = 1; i <= 200; ++i)
        for (int j = 1; j <= i; ++j)
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * j) % modu;

    while(n > 0 && m > 0){
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            ans = (ans + dp[m][i]) % modu;

        printf("%d\n", ans);
        scanf("%d %d", &n, &m);
    }
}

TIOJ 1043 F.名偵探蚵男

#include <cstdio>
#include <cstdlib>
#include <string.h>
#define INT64 long long
using namespace std;

INT64 dp[100005];

int main(){
    int n, p, t;
    scanf("%d %d", &n, &p);

    while(n > 0 && p > 0){
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        
        for (int i = 0; i < n; ++i){
            scanf("%d", &t);
            for (int j = 1; j <= p; ++j)
                if(j - t >= 0)
                    dp[j] += dp[j - t];
        }
        printf("%lld\n", dp[p]);
        scanf("%d %d", &n, &p);
    }
}

TIOJ 1406 魚 FISH

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define INT64 long long
using namespace std;

int n;
INT64 x[100005], y[100005];

bool check(INT64 t){
    INT64 now = y[0] - t;
    for (int i = 1; i < n; ++i){
        if(now > x[i] - x[i - 1])
            now = y[i] - t + now - x[i] + x[i - 1];
        else if(now < 0)
            now = y[i] - t + now + x[i - 1] - x[i];
        else
            now = y[i] - t;
    }
    if(now >= 0)
        return true;
    return false;
}

int main(){
    while(scanf("%d",&n) != EOF ){
        INT64 r = 0, l = 0;
        for (int i = 0; i < n; ++i){
            scanf("%lld %lld",&x[i],&y[i]);
            if(y[i] > r)
                r = y[i];
        }
        while(l < r){
            INT64 mid = (l+r)/2 + 1;
            if(check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        printf("%lld\n", l);
    }
}

TIOJ 1355 河內之塔-蘿莉塔

#include <cstdio>
#include <cstdlib>
int step;
void ho(int n, int a, int b, int c){
    if(n == 1)
        printf("#%d : move the dish from #%d to #%d \n",step++, a ,c);
    
    else{
        ho(n-1, a, c, b);
        ho(1, a, b, c);
        ho(n-1, b, a, c);
    }
}

int main(){
    int n;
    scanf("%d",&n);
    step = 1;
    ho(n, 1, 2, 3);
}

TIOJ 1306 字串中的字串

#include <cstdio>
#include <cstdlib>
#include <string.h>
#define INT64 long long

char s[10005], p[10005];
const INT64 modu = 1e9+7;
INT64 hash[10005];
INT64 modu26[10005];

int main(){
    int T;
    scanf("%d",&T);

    modu26[0] = 1;
    for (int i = 1; i <= 10000; ++i)
        modu26[i] = (modu26[i-1] * 26) % modu;
    
    while(T--){
        scanf("%s",s);
        hash[0] = 0;
        for (int i = 1; i <= strlen(s); ++i)
            hash[i] = (hash[i-1] * 26 + s[i-1] - 'a' + 1) % modu;

        int n;
        scanf("%d",&n);
        while(n--){
            scanf("%s",p);
            int l = strlen(p);
            INT64 p_hash = 0;
            int ans = 0;
            for (int i = 0; i < l; ++i)
                p_hash = (p_hash * 26 + p[i] - 'a' + 1) % modu;

            for (int i = 0; i + l <= strlen(s); ++i){
                INT64 now = (hash[i+l] - hash[i] * modu26[l]) % modu;
                if(now < 0)
                    now += modu;
                if(p_hash == now)
                    ans ++;
            }
            printf("%d\n", ans);
        }
    }
}