Yu Code

2015年5月27日星期三

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");

}

2015年4月13日星期一

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);
    }  
}

2015年4月10日星期五

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);
    }
}

2015年4月9日星期四

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);
}

2015年5月27日 星期三