Codeforces Round #277.5 (Div. 2), problem: (E) Hiking

類似最優比率樹

二分搜+dp

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define EPS 0.000000001
#define INF 1000000000
using namespace std;
double val[1011];
int from[1011];
int x[1011], b[1011];
int main()
{
    int n, ll; scanf("%d %d", &n, &ll);
    double l = (double)ll;
    x[0] = 0, b[0] = 0;
    for(int lx = 1;lx <= n;lx++)
        scanf("%d %d", x+lx, b+lx);
    val[0] = 0;
    double fmin = 0, fmax = x[n];
    while(fmax - fmin > EPS){
//        printf("%f\n", fmax);
        double ftest = (fmax+fmin)/2;
        for(int lx = 1;lx <= n;lx++){
            val[lx] = INF;
            for(int ly = 0;ly < lx;ly++)
                val[lx] = min(val[lx], 
                sqrt(fabs((double)(x[lx]-x[ly]-ll)))-ftest*(double)(b[lx]) + val[ly]);
        }
        if(val[n] > 0)
            fmin = ftest;
        else
            fmax = ftest;
    }
    from[0] = -1;
    for(int lx = 1;lx <= n;lx++){
        val[lx] = INF;
        for(int ly = 0;ly < lx;ly++){
            double cal = sqrt(fabs((double)(x[lx]-x[ly]-ll)))-fmin*(double)(b[lx]) + val[ly];
            if(val[lx] > cal)
                from[lx] = ly, val[lx] = cal;
        }
    }
    int path[1011], pathcnt = 0;
    int prc = n;
    while(prc != 0){
        //printf("prc = %d\n", prc);
        path[pathcnt++] = prc;
        prc = from[prc];
    }
    for(int lx = pathcnt-1;lx >= 0;lx--)
        printf("%d ", path[lx]);
    printf("\n");
    return 0;
}

Codeforces Round #277.5 (Div. 2), problem: (D) Unbearable Controversy of Being

ㄘ屌屌囉

數一數 a-> ? -> b的個數

include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long int int64;
vector<int> to[3010];
int main()
{
    int n, k; scanf("%d %d", &n, &k);
    for(int lx = 0;lx < k;lx++){
        int a, b;
        scanf("%d %d", &a, &b);
        to[a-1].push_back(b-1);
    }
    int64 count = 0;
    int64 cnt[3010];
    for(int lx = 0;lx < n;lx++){
        //printf("prc on %d\n", lx);
        int qs = 0, qe = 1;
        memset(cnt, 0, sizeof(cnt));
        for(int xx = 0;xx < to[lx].size();xx++){
            int prc = to[lx][xx];
            for(int yy = 0; yy < to[prc].size(); yy++)
                cnt[to[prc][yy]]++;
        }
        for(int xx = 0;xx < n;xx++){
            if(xx == lx) continue;
            //printf("count to %d -> %I64d\n", xx, cnt[xx]);
            count += cnt[xx]*(cnt[xx]-1)/2;
        }
    }
    printf("%I64d\n", count);
//    for(;;);
    return 0;
}

POJ 3481 Double Queue

#include<cstdio>
#include<cstdlib>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
int main(){
    int op, k, p;
    set<pii> que;
    for(;;){
        scanf("%d", &op);
        if(op == 0) break;
        if(op == 1){
            scanf("%d %d", &k, &p);
            que.insert(pii(p, k));
        }else if(op == 2){
            if(que.size() == 0)
                puts("0");
            else{
                set<pii>::iterator get = que.end();
                get--;
                printf("%d\n", get->second);
                que.erase(*get);
            }
        }else{
            if(que.size() == 0)
                puts("0");
            else{
                set<pii>::iterator get = que.begin();
                printf("%d\n", get->second);
                que.erase(*get);
            }
        }
    }
    return 0;
}

Codeforces Round #278 (Div. 1), problem: (B) Strip

遞增區間，雖然比賽時寫二分搜

有點G
設錯INF
Pretest 過
System 沒過

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 1000000001
using namespace std;
typedef long long int int64;
int tmin[600000];
int tmax[600000];
int arr[100000];
int base;
void init(int n){
    base = (1<<(int)(ceil(log2(n+4)))) - 1;
    for(int lx = 1;lx <= 2*base+1;lx++)
        tmin[lx] = INF, tmax[lx] = -INF;

    for(int lx = 0;lx < n;lx++)
        tmin[base+lx+2] = arr[lx],
        tmax[base+lx+2] = arr[lx];

    for(int lx = base;lx;lx--){
        tmin[lx] = min(tmin[lx+lx], tmin[lx+lx+1]);
        tmax[lx] = max(tmax[lx+lx], tmax[lx+lx+1]);
    }
    return;
}
int qdet(int a, int b){
    a+=2, b+=2;
    int gmin = INF, gmax = -INF;
    for(a += base-1, b += base+1;a^b^1;a>>=1, b>>=1){
        if(~a&1) gmin = min(gmin, tmin[a^1]), gmax = max(gmax, tmax[a^1]);
        if(b&1) gmin = min(gmin, tmin[b^1]), gmax = max(gmax, tmax[b^1]);
    }
    return gmax-gmin;
}
int dp[100003];
int cut[100003]; int ccut = 0;
int main()
{
    int n, s, l;
    scanf("%d %d %d", &n, &s, &l);
    for(int lx = 0;lx < n;lx++)
        scanf("%d", arr+lx);
    init(n);
    int ptr = 0;
    cut[0] = -1;ccut++;
    for(int lx = 0;lx < n;lx++){
        //printf("%d\n", lx);
        for(;ptr < ccut;ptr++)
            if(qdet(cut[ptr]+1, lx) <= s)
                break;
        if(lx-cut[ptr]>= l and qdet(cut[ptr]+1, lx) <= s){
            //printf("find cut %d at %d\n", cut[right], right);
            if(cut[ptr] == -1)
                dp[lx] = 1;
            else
                dp[lx] = 1+dp[cut[ptr]];
            cut[ccut++] = lx;
        }else
            dp[lx] = -1;
        //printf("dp%d = %d\n", lx , dp[lx]);
    }
    printf("%d\n", dp[n-1]);
    return 0;
}

Codeforces Round #278 (Div. 1), problem: (C) Prefix Product Sequence

i/(i-1) = j/(j-1) mod p,  p>=3 <=> i = j for p-1>= i >= j >= 2


這題在比賽時最後十五分鐘才打開看到

早知道就先來認真想= =

不過，把1, 4特例忽略掉真的頗G，一下就被Hack掉

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
int seive[100005] = {0};
int64 p;
int64 func(int64 a, int n){
    if(n == 0) return 1;
    if(n == 1) return a;
    int64 gg = func(a, n/2);
    gg = (gg*gg)%p;
    if(n%2 == 0) return gg;
    if(n%2 == 1) return (gg*a)%p;
}
int main()
{
    for(int lx = 2;lx <= 100000;lx++)
        if(seive[lx] == 0)
            for(int ly = 2;ly*lx <= 100000;ly++)
                seive[ly*lx] = 1;
    scanf("%I64d", &p);
    if(p <= 4){
        puts("YES");
        if(p == 1)
            printf("1\n");
        else if(p == 2)
            printf("1\n2\n");
        else if(p == 3)
            printf("1\n2\n3\n");
        else
            printf("1\n3\n2\n4\n");
        return 0;
    }
    if(seive[p]){
        puts("NO");
        return 0;
    }
    puts("YES");
    printf("1\n");
    for(int64 lx = 2;lx < p;lx++){
        printf("%I64d\n", (lx*func(lx-1, p-2))%p);
    }
    printf("%I64d\n", p);
    return 0;
}

Codeforces Round #278 (Div. 1), problem: (A) Fight the Monster

頗有趣的題目，Greedy 亂掃

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 1000000000
using namespace std;
typedef long long int int64;
int main()
{
    int h0, a0, d0;
    int h, a, d;
    int ch, ca, cd;
    int prespend = 0;
    scanf("%d %d %d", &h, &a, &d);
    scanf("%d %d %d", &h0, &a0, &d0);
    scanf("%d %d %d", &ch, &ca, &cd);
    if(a <= d0){
        prespend = ca*(d0+1-a);
        a = d0+1;
    }
    int minspend = INF;
    for(int lx = 0; h0+2 >= a+lx-d0;lx++){
        for(int ly = 0;a0+2 >= d+ly;ly++){
            int aa = a+lx, dd = d+ly;
            int hh = (h0+aa-d0-1)/(aa-d0)*(a0-min(a0,dd));
            int dh = max(hh+1, h) - h;
            minspend = min(lx*ca + ly*cd + dh*ch + prespend, minspend);
        }
    }
    printf("%d\n", (minspend == INF) ? prespend:minspend);
    return 0;
}

TIOJ 1210 圖論 之 簡單圖測試

Havel定理：對於一個簡單圖的等價條件


看到有人做到 XX ms，實在不知道QQ

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
typedef pair<int,int> pii;
int arr[10020];
int tmp[10020];
int main()
{
 int n;
 for(;;){
  scanf("%d", &n);
  if(n == 0) break;
  memset(arr, 0, sizeof(arr));
  int get_max = -1;
  int sum = 0;
  for(int lx = 0;lx < n;lx++){
   int inp;scanf("%d", &inp);
   arr[inp]++;
   get_max = max(get_max, inp);
   sum ^= inp&1;
  }
  if(sum&1 == 1){
   puts("No");
   continue;
  }
  bool ok = true;
  for(int lx = get_max;lx >= 0 and ok;){
   /*for(int ly = 0;ly <= get_max;ly++){
    printf("%d->%d ", ly, arr[ly]);
   }
   printf("\n");*/
   if(arr[lx] == 0){lx--; continue;}
   int pcnt = lx;
   arr[lx]--;
   for(int ly = lx;ly >= 1;ly--){
    if(arr[ly] >= pcnt){
     tmp[ly-1] = pcnt;
     arr[ly] -= pcnt;
     pcnt = 0;
    }else{
     tmp[ly-1] = arr[ly];
     pcnt -= arr[ly];
     arr[ly] = 0;
    }
   }
   for(int ly = lx-1;ly >= 0;ly--)
    arr[ly] += tmp[ly];
   if(pcnt > 0)
    ok = false;
  }
  if(arr[0] < 0) ok = false;
  puts(ok ? "Yes":"No");
 }
 return 0;
}