17国庆day3

2015-2016 Northwestern European Regional Contest (NWERC 2015)

Elementary Math

题意:给n组数, 可以加三种(加减乘)运算, 使得所有的结果都不相同. 如果不存在则输出impossible.

二分图匹配, 每一组数像不同的结果连边, 求最大匹配,如果最大匹配等于n则有解.

其实还是比较裸的,场上只想到暴力=_=

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define ll long long
  4 const int maxe = 8000;
  5 const int maxn = 2510;
  6 
  7 map<ll,int> mp;
  8 ll A[maxe];
  9 ll p1[maxn], p2[maxn];
 10 
 11 struct Edge{
 12     int u,v,nex;
 13     Edge(int u=0,int v=0,int nex=0): u(u), v(v), nex(nex) {}
 14 }e[maxe];
 15 int head[maxn];
 16 int cnt;
 17 void init(){
 18     memset(head, -1, sizeof(head));
 19     cnt = 0;
 20 }
 21 void add(int u,int v) {
 22     e[cnt] = Edge(u,v,head[u]);
 23     head[u] = cnt++;
 24 }
 25 
 26 int vg[maxn], vb[maxe], mcg[maxn], mcb[maxe];
 27 
 28 int Hungary(int u){
 29     vg[u] = 1;
 30     for(int i = head[u]; ~i; i = e[i].nex) {
 31         int v = e[i].v;
 32         if(!vb[v]) {
 33             vb[v] = 1;
 34             if(mcb[v] == -1 || Hungary(mcb[v])){
 35                 mcb[v] = u;
 36                 mcg[u] = v;
 37                 return 1;
 38             }
 39         }
 40     }
 41     return 0;
 42 }
 43 
 44 int main() {
 45     int n;
 46     while(scanf("%d", &n)!=EOF) {
 47         init();
 48         mp.clear();
 49         ll a, b;
 50         int id = 0;
 51         for(int i = 0; i < n; i++) {
 52             scanf("%lld %lld", &a, &b);
 53             p1[i] = a;
 54             p2[i] = b;
 55             ll u = a+b;
 56             if(!mp.count(u)) {
 57                 A[id] = u;
 58                 mp[u] = id++;
 59             }
 60             add(i, mp[u]);
 61             u = a-b;
 62             if(!mp.count(u)) {
 63                 A[id] = u;
 64                 mp[u] = id++;
 65             }
 66             add(i, mp[u]);
 67             u = a*b;
 68             if(!mp.count(u)) {
 69                 A[id] = u;
 70                 mp[u] = id++;
 71             }
 72             add(i, mp[u]);
 73         }
 74         int ans = 0;
 75         memset(mcb, -1, sizeof(mcb));
 76         memset(mcg, -1, sizeof(mcg));
 77         for(int i = 0; i < n; i++) {
 78             memset(vb, 0, sizeof(vb));
 79             memset(vg, 0, sizeof(vg));
 80             if(Hungary(i)) ans++;
 81         }
 82        // cout<<ans<<endl;
 83         if(ans != n) {
 84             puts("impossible");
 85             continue;
 86         }
 87         for(int i = 0; i < n; i++) {
 88             int v = mcg[i];
 89             if(p1[i]+p2[i] == A[v]) {
 90                 printf("%lld + %lld = %lld
", p1[i], p2[i], A[v]);
 91                 continue;
 92             } else if(p1[i]-p2[i] == A[v]){
 93                 printf("%lld - %lld = %lld
", p1[i], p2[i], A[v]);
 94                 continue;
 95             } else {
 96                 printf("%lld * %lld = %lld
", p1[i], p2[i], A[v]);
 97                 continue;
 98             }
 99         }
100     }
101     return 0;
102 }

View Code

Debugging

Gym - 101485D

题意:n行代码,有一个bug,可以输出中间结果debug, 每加一行printf语句耗时b, 编译一次耗时a,问最短多长时间找到bug.

dp[n]表示n行需要的时间, 暴力把n行分成2到n段,取最小的时间就是结果.

刚看到这道题的时候以为和高楼抛水球那个题一样......没绕出来......

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn = 1e6+10;
 5 const ll inf = 1e16;
 6 ll d[maxn];
 7 ll n, a, b;
 8 
 9 ll solve(ll n) {
10     if(n <= 1) return 0;
11     if(d[n]) return d[n];
12     ll res = inf;
13     for(ll i = 2; i <= n; i++) {
14         res = min(res, solve(ceil((double)n/i))+b*(i-1)+a);
15     }
16     return d[n]=res;
17 }
18 
19 int main() {
20     while(scanf("%lld %lld %lld", &n, &a, &b)!=EOF) {
21         printf("%lld
", solve(n));
22     }
23 }

View Code