Elementary Math

 

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

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

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

1 #include 
      
         2 using namespace std;  3 #define ll long long  4 const int maxe = 8000;  5 const int maxn = 2510;  6   7 map
       
         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<
        
         <
        
       
      

 

Debugging

 

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

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

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

1 #include 
      
        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\n", solve(n));22     }23 }