1、下单

给定若干商品，可以选择打折、满减两种方式。

#include 
    
     #include 
     
      #include 
      
       using namespace std;struct Manjian {  int x, y;};const int N = 107;const int M = 1007;int price[N];int can[N];Manjian manjian[M];int n, m;int main() { // freopen("in.txt", "r", stdin);  cin >> n >> m;  for (int i = 0; i < n; i++) {    cin >> price[i] >> can[i];  }  for (int i = 0; i < m; i++) {    cin >> manjian[i].x >> manjian[i].y;  }  double useZheco = 0;  for (int i = 0; i < n; i++) {    if (can[i]) {      useZheco += 0.8 * price[i];    }else{        useZheco+=price[i];    }  }  double jian = 0xfffffff;  double s = 0;  for (int i = 0; i < n; i++) s += price[i];  for (int i = 0; i < m; i++) {    if (manjian[i].x <= s) {      jian = min(s - manjian[i].y, jian);    }  }  double ans = min(jian, useZheco);  printf("%.2f\n",ans);  return 0;}

2、买可乐

此题看上去可乐可以买多种，实际上只能买一种。因为每种可乐都是不限数量的，如果限制数量那也很简单，也是一个排序问题。

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXN=1e4+7;int n,m,k;int a[MAXN],b[MAXN];int buy[MAXN];double good(int x){    return a[x]*m+b[x]*(n-m);}int main() {  //freopen("in.txt", "r", stdin);  cin>>n>>m>>k;  int ans=0;  for(int i=0;i
       
        >a[i]>>b[i];  }  for(int i=0;i
        
         =good(ans)){          ans=i;      }  }  buy[ans]=n;  cout<

3、世界杯足球赛

16支球队组成一颗4层的二叉树，求每支球队到达根的概率。

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXN = 1e4 + 7;double a[17][17];struct Node {  double a[17];};Node b[100];void solve(int x) {  for (int i = 0; i < 16; i++) b[x].a[i] = 0;  if (x >= 16) {    b[x].a[x - 16] = 1;  } else {    solve(x << 1);    solve((x << 1) | 1);    for (int i = 0; i < 16; i++) {      for (int j = 0; j < 16; j++) {        b[x].a[i] += a[i][j] * b[x << 1].a[i] * b[x << 1 | 1].a[j];        b[x].a[j] += a[j][i] * b[x << 1].a[i] * b[x << 1 | 1].a[j];      }    }  }  //cout<
       
        <
        
         > a[i][j];    }  }  solve(1);  cout << b[1].a[0];  for (int i = 0; i < 16; i++) {    cout << " " << b[1].a[i];  }  cout << endl;  return 0;}

4、MedoC资格赛

这道题坑有不少，如果实在不知道哪里错了，重写一遍。

人脑读代码时总是有一种惰性，因此无法发现隐含的bug。人读代码时，容易被代码牵着思路走。

而写代码时，人脑是主动输出的。

这道题注意点如下：

每轮比赛的权值不能出现浮点，出现浮点后可能会造成结果不精确。实际上，这道题的权值使用long就能够存下了。第i轮资格赛更新后的权值为$w_i^'=prod/roundMax_i\prodw_i$

排名并列就是不确定能否出线，如果第k+1名的成绩不等于第k名，那么这些并列第k名的都是稳赢。

胜负和的判断
在任何情形下都胜利的人就是胜利；
在任何情形下都失败的人就是失败；
其余情况，就是不太确定的情况。

需要分两种情况考虑，有没有不确定量
如果存在-1，那么需要枚举这个人所能够取得的一切成绩
如果不存在-1，那么只需要考虑当前情况即可
这道题只有一个-1，真的是已经非常友好了。

只看首尾是错误的
比如C的取值为50,那么只看C=0和C=50两种情况是不够的，结果是错误的。
因为C的取值可能影响比赛各个轮次的权重，从而影响每个人的成绩。

import java.util.Arrays;import java.util.Scanner;public class Main {int n, m, k, C;final int MAX_N = 507;final int MAX_M = 7;int w[] = new int[MAX_M];long a[][] = new long[MAX_N][MAX_M];int res[][] = new int[MAX_N][MAX_N];//每轮是否能够胜出final int WIN = 1, LOSE = 2, PEACE = 3;class Pair {    int ind;    long value;    Pair(int ind, long value) {        this.ind = ind;        this.value = value;    }    @Override    public String toString() {        return String.format("%d %d", ind, value);    }}void solve(int[] res) {    long[] we = new long[MAX_M];    long[] ma = new long[MAX_M];    for (int i = 0; i < n; i++)        for (int j = 0; j < m; j++)            ma[j] = Math.max(ma[j], a[i][j]);    long prod = 1;    for (int i = 0; i < m; i++)        if (ma[i] > 0)            prod *= ma[i];    for (int i = 0; i < m; i++)        if (ma[i] > 0) we[i] = prod / ma[i] * w[i];        else we[i] = 0;    long[] score = new long[MAX_N];    for (int i = 0; i < n; i++)        for (int j = 0; j < m; j++)            if (ma[j] > 0)                score[i] += we[j] * a[i][j];    Pair pairs[] = new Pair[MAX_N];    for (int i = 0; i < n; i++) pairs[i] = new Pair(i, score[i]);    Arrays.sort(pairs, 0, n, (o1, o2) -> {        if (o1.value < o2.value) return 1;        else if (o1.value == o2.value) return 0;        else return -1;    });    int unsureBeg = k - 1, unsureEnd = k - 1;    while (unsureBeg >= 0 && pairs[unsureBeg].value == pairs[k - 1].value) unsureBeg--;    while (unsureEnd < n && pairs[unsureEnd].value == pairs[k - 1].value) unsureEnd++;    if (unsureEnd == k) unsureBeg = k - 1;    for (int i = 0; i <= unsureBeg; i++) res[pairs[i].ind] = WIN;    for (int i = unsureBeg + 1; i < unsureEnd; i++) res[pairs[i].ind] = PEACE;    for (int i = unsureEnd; i < n; i++) res[pairs[i].ind] = LOSE;//    for (int i = 0; i < n; i++) {//        System.out.println(pairs[i]);//    }//    for (int i = 0; i < n; i++) {//        System.out.print(res[i] + " ");//    }//    System.out.println("==============");}boolean all(int x, int y) {    for (int j = 0; j <= C; j++)        if (res[j][x] != y)            return false;    return true;}Main() {    Scanner cin = new Scanner(System.in);    n = cin.nextInt();    m = cin.nextInt();    k = cin.nextInt();    C = cin.nextInt();    for (int i = 0; i < m; i++) w[i] = cin.nextInt();    int badX = -1, badY = -1;    for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            a[i][j] = cin.nextInt();            if (a[i][j] == -1) {                badX = i;                badY = j;            }        }    }    if (badX == -1) {        solve(res[0]);        for (int i = 0; i < n; i++) {            System.out.println(res[0][i]);        }    } else {        for (int i = 0; i <= C; i++) {            a[badX][badY] = i;            solve(res[i]);        }        for (int i = 0; i < n; i++) {            if (all(i, WIN)) {                System.out.println(WIN);            } else if (all(i, LOSE)) {                System.out.println(LOSE);            } else {                System.out.println(PEACE);            }        }    }    cin.close();}public static void main(String[] args) {    new Main();}}

5、万无一失的旅行方案

这道题对了一半。

要保证最优路径中的每一站都能换乘，其实能否换乘是由城市决定的，一个城市有一个最晚出发时间，大于最晚出发时间的车次是无论如何不能订票的，因为大于最晚出发时间的车次是用来改签的。

首先，从n号结点出发用队列搜索一遍，初始化每个城市的最晚出发时间；

然后，从n号结点出发用队列搜索一遍，求dp[城市][出发时间]

#include
    
     #include
     
      #include
      
       using namespace std;const int MAXN =507;//最大结点数const int MAXM = 15007;//最大边数const int MAXTIME = 49;//最大时间struct Edge {    int x, y,c,ts,td;//出发地，目的地，花费，出发时间，到达时间};Edge g[MAXN][MAXM];//g[i][j]表示到达结点i的第j条边int startTime[MAXN];//每个结点的最晚出发时间（可以去等号），晚于此时间没有备选方案int len[MAXN]; //len[i]表示到达结点i的边数int n,m;   //n个结点，m条边int dp[MAXN][MAXTIME];//动态规划，dp[i][j]表示在j时间出发，从城市i到达n所需要的最少花费const int MAXCOST = 1007 * MAXM;//花费的上界//自定义队列struct Queue {    int a[MAXN];    bool inq[MAXN];//每个元素只进队列一次    int head = 0;    int tail = 0;    void init() {        head = 0;        tail = 0;        for (int i = 0; i < MAXN; i++)inq[i] = false;    }    void enq(int x) {        if (inq[x]) return;        a[tail] = x;        inq[x] = 1;        tail = (tail + 1) % MAXN;    }    int deq() {        int ans = a[head];        head = (head + 1) % MAXN;        inq[ans] = 0;        return ans;    }    bool empty() {        return head == tail;    }}q;void showEdge(Edge &e) {    printf("%d(%d)-%d->%d(%d) ", e.x, e.ts, e.c, e.y, e.td);}void showNode(int city) {    cout << "city " << city << " startTime " << startTime[city] << endl;    for (int i = 0; i < len[city]; i++) {        if (g[city][i].ts > startTime[g[city][i].x]) {            cout << " [start late] ";        }        showEdge(g[city][i]);        if (g[city][i].td > startTime[city] - 1) {            cout << " [reach late] ";        }    }    puts("");}void showGraph() {    for (int i = 1; i <= n; i++) {        showNode(i);    }    puts("================");}//计算从每个城市出发的最晚时间void cutEdges() {    //每个城市的出发时间    for (int i = 0; i < n; i++) {        startTime[i] = -1;//出发时间初始化为尽量小    }    //目的结点入队    startTime[n] = MAXTIME;    q.init();    q.enq(n);    while (!q.empty()) {        int now=q.deq();         for (int i = 0; i < len[now]; i++) {            Edge* e = &g[now][i];             if (e->td < startTime[e->y]-1) {//到达时间必须早于目的地的出发时间                int ts = e->ts - 1;//-1表示留下改签的时间                 if (startTime[e->x] < ts) {                    q.enq(e->x);                    startTime[e->x] = ts;                }            }        }    }}void update(int city, int startTime, int cost) {    for (int i = 0; i <= startTime; i++) {        dp[city][i] = min(dp[city][i], cost);    }}void solve() {     for (int i = 0; i < n; i++) {        for (int j = 0; j <= MAXTIME; j++) {            dp[i][j] = MAXCOST;        }    }    for (int i = 0; i <= MAXTIME; i++)dp[n][i] = 0;    q.init();    q.enq(n);    while (!q.empty()) {        int now = q.deq();         for (int i = 0; i < len[now]; i++) {            Edge*e = &g[now][i];             //如果到达时间太晚，直接跳出            if (e->td >= startTime[e->y]) break;            //如果出发时间太晚，继续循环            if (e->ts > startTime[e->x])continue;            int co = e->c + dp[e->y][e->td+1];             if (co < dp[e->x][e->ts]) {                update(e->x, e->ts, co);                q.enq(e->x);            }        }    }}int comp(const void *x,const void *y) {    Edge *xx = (Edge*)x;    Edge *yy = (Edge *)y;    return xx->td-yy->td;}void sortEdges() {    for (int i = 1; i <= n; i++) {        qsort(g[i], len[i], sizeof(Edge), comp);    }}void showDp() {    cout << "DP is:" << endl;    for (int i = 1; i <= n; i++) {        for (int j = 0; j < MAXTIME; j++) {            cout << dp[i][j] << " ";        }        cout << endl;    }}int main() {    freopen("in.txt", "r", stdin);     scanf("%d%d", &n,&m);    for (int i = 0; i < m; i++) {        int x,y,c ,h1, m1, h2, m2;        scanf("%d%d%d%d:%d%d:%d",&x,&y,&c,&h1,&m1,&h2,&m2);         Edge *e = &g[y][len[y]++];        e->x = x;        e->y = y;        e-> c = c;        e->ts = h1 << 1 | (m1==30?1:0);        e->td = h2 << 1 | (m2 == 30 ? 1 : 0);    }     sortEdges();     cutEdges();     solve();     int ans = MAXCOST;    for (int i = 0; i < MAXTIME; i++) {        ans = min(dp[1][i],ans);    }    if (ans == MAXCOST)ans = -1;    cout << ans << endl;    return 0;}

编程时，多打印些东西，多写点注释，多重构或重写，就容易发现bug。

转载地址：http://ontkm.baihongyu.com/

你可能感兴趣的文章