第三周 3.13-3.19

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 int main(void)
 6 {
 7     int T;
 8     scanf("%d", &T);
 9     while(T--)
10     {
11         int x, ans = 0;
12         scanf("%d", &x);
13         for(int i = 1; i <= x; i++) ans = (ans + x + 1) % i;
14         printf("%d\n", ans + 1);
15     }
16     return 0;
17 }

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #include <algorithm>
  6 using namespace std;
  7 int p[222], s[11], t[11];
  8 
  9 //SPFA_min_cost_flow
 10 const int INF = 1e9;
 11 const int maxn = 1e5 + 10;
 12 int dist[maxn], vis[maxn];
 13 int pv[maxn], pe[maxn];
 14 int cnt, h[maxn];
 15 
 16 struct edge
 17 {
 18     int to, pre, cap, cost;
 19 } e[maxn<<1];
 20 
 21 void init()//Don‘t forget
 22 {
 23     cnt = 0;
 24     memset(h, -1, sizeof(h));
 25 }
 26 
 27 void add(int from, int to, int cap, int cost)
 28 {
 29     e[cnt].pre = h[from];
 30     e[cnt].to = to;
 31     e[cnt].cap = cap;
 32     e[cnt].cost = cost;
 33     h[from] = cnt;
 34     cnt++;
 35 }
 36 
 37 void ad(int from, int to, int cap, int cost)
 38 {
 39     add(from, to, cap, cost);
 40     add(to, from, 0, -cost);
 41 }
 42 
 43 int min_cost_flow(int s, int t, int f)
 44 {
 45     int ret = 0;
 46     while(f > 0)
 47     {
 48         memset(vis, 0, sizeof(vis));
 49         for(int i = 0; i < maxn; i++) dist[i] = INF;
 50         dist[s] = 0;
 51         queue<int> q;
 52         q.push(s);
 53         while(!q.empty())
 54         {
 55             int v = q.front(); q.pop();
 56             vis[v] = 0;
 57             for(int i = h[v]; i >= 0; i = e[i].pre)
 58             {
 59                 int to = e[i].to, cap = e[i].cap, cost = e[i].cost;
 60                 if(cap > 0 && dist[to] > dist[v] + cost)
 61                 {
 62                     pv[to] = v, pe[to] = i;
 63                     dist[to] = dist[v] + cost;
 64                     if(!vis[to]) q.push(to);
 65                     vis[to] = 1;
 66                 }
 67             }
 68         }
 69 
 70         if(dist[t] == INF) return -1;//modify here
 71 
 72         int d = f;
 73         for(int v = t; v != s; v = pv[v])
 74             d = min(d, e[pe[v]].cap);
 75         f -= d;
 76         ret += d * dist[t];
 77         for(int v = t; v != s; v = pv[v])
 78         {
 79             e[pe[v]].cap -= d;
 80             e[pe[v]^1].cap += d;
 81         }
 82     }
 83     return ret;
 84 }
 85 
 86 int main(void)
 87 {
 88     int T;
 89     scanf("%d", &T);
 90     while(T--)
 91     {
 92         init();
 93         int n, k, m, P, Q, sum = 0;
 94         scanf("%d %d", &n, &k);
 95         for(int i = 1; i <= n; i++) scanf("%d", p + i), sum += p[i];
 96         scanf("%d %d %d", &m, &P, &Q);
 97         for(int i = 1; i <= m; i++) scanf("%d %d", s + i, t + i);
 98         int st = 2 * n + 1, ed = st + 1;
 99         for(int i = 1; i <= n; i++) ad(st, i, p[i], 0);
100         for(int i = 1; i <= n; i++) ad(i + n, ed, p[i], 0);
101         ad(st, 1 + n, k, 0);
102         for(int i = P; i <= n; i++) ad(st, i + n, INF, Q);
103         for(int i = 1; i < n; i++) ad(i, i + 1, INF, 0);
104         for(int i = 1; i < n; i++) ad(i + n, i + n + 1, INF, 0);
105         for(int i = 1; i <= m; i++)
106             for(int j = 1; j + t[i] <= n; j++)
107                 ad(j, j + t[i] + n, INF, s[i]);
108         int ans = min_cost_flow(st, ed, sum);
109         if(ans == -1) puts("No solution");
110         else printf("%d\n", ans);
111     }
112     return 0;
113 }