首页 > 代码库 > 2015ACM/ICPC亚洲区沈阳站

2015ACM/ICPC亚洲区沈阳站

5510  Bazinga

题意:给出n个字符串,求满足条件的最大下标值或层数

        条件:该字符串之前存在不是 它的子串 的字符串

求解si是不是sj的子串,可以用kmp算法之类的。

strstr是黑科技,比手写的kmp快。if(strstr(s[i], s[j]) == NULL),则Si不是Sj的子串。

还有一个重要的剪枝:对于一个串,如果当前找到的串是它的母串,则下一次这个串不用遍历。

 1 #include <set> 2 #include <queue> 3 #include <cstdio> 4 #include <vector> 5 #include <cstring> 6 #include <algorithm> 7 using namespace std; 8 typedef long long LL; 9 #define mem(x,y) memset(x, y, sizeof(x))10 #define lson l,m,rt << 111 #define rson m+1,r,rt << 1 | 112 int gcd(int a,int b){return b == 0 ? a : gcd(b, a % b);}13 int lcm(int a,int b){return a / gcd(a, b) * b;}14 15 int T, n;16 char s[505][2005];17 int vis[505];18 19 int main()20 {21     scanf("%d", &T);22     for(int Case = 1; Case <= T; Case++)23     {24         mem(vis, 0);25         scanf("%d", &n);26         getchar();27         for(int i = 1; i <= n; i++)28         {29             scanf("%s", s[i]);30         }31         int ans = -1;32         for(int i = 2; i <= n; i++)33         {34             int ok = 0;35             for(int j = i - 1; j >= 1; j--)36             {37                 if(vis[j]) continue;38                 if(strstr(s[i], s[j]) == NULL)//sj 不是 si的子串39                 {40                     ok = 1;41                     break;42                 }43                 else44                 {45                     vis[j] = 1;//重要剪枝46                 }47             }48             if(ok) ans = i;49         }50         printf("Case #%d: %d\n", Case, ans);51     }52     return 0;53 }

 

 

5512  Pagodas

题意:有n个庙经过长时间风吹雨打需要修补,只有两座(被标记为a,b)完好无损不需要修补,有两个和尚轮流去修补这n-2个庙,每个和尚每次只能修补一个庙标记为i,并要求i满足i=j+k或者i=j-k,每个庙只能被修建一次;其中j和k代表已经修建好的庙,Yuwgna先开始,问最后谁不能修建谁输;

更相减损术!(gcd里头:辗转相除法,更相减损术,自行百度)

更相减损术:

第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
所以它在1-n里头,只要是它的最小公因数的倍数的数都是可以选择的点,所以答案是n / gcd(x, y)
主要是由i = j - k联想出来的。
 1 #include <set> 2 #include <queue> 3 #include <cstdio> 4 #include <vector> 5 #include <cstring> 6 #include <algorithm> 7 using namespace std; 8 typedef long long LL; 9 #define mem(x,y) memset(x, y, sizeof(x))10 #define lson l,m,rt << 111 #define rson m+1,r,rt << 1 | 112 int gcd(int a,int b){return b == 0 ? a : gcd(b, a % b);}13 int T, n, x, y;14 15 int main()16 {17     scanf("%d", &T);18     for(int Case = 1; Case <= T; Case++)19     {20         scanf("%d%d%d", &n, &x, &y);21         int g = gcd(x, y);22         int cnt = n / g;23         printf("Case #%d: ", Case);24         printf("%s\n", cnt & 1 ? "Yuwgna" : "Iaka");25     }26     return 0;27 }

 

 

 

5521  Meeting

题意:给你一个n个点,m个集合的图,每个集合中的点都可以以di的距离相互的到达,问你两个人同时从1和n出发,会在那个点相遇。

每个集合内部里的所有的边都是互通的,如果一个个连就要n²了,可以采用增加虚拟结点的方式,来减少点。虚拟一个s,一个e,把他们连接起来。

 

 1 for(int i = 1; i <= m; i++) 2 { 3     int w, num; 4     int s = n + i, e = n + i + m; 5     scanf("%d%d", &w, &num); 6  G[s].push_back(edge(e, w)); 7     while(num--) 8     { 9         int x;10         scanf("%d", &x);11         G[e].push_back(edge(x, 0));12         G[x].push_back(edge(s, 0));13     }14 }

 

 

 

 

  1 //题意:给你一个n个点,m个集合的图,每个集合中的点都可以以di的距离相互的到达,问你两个人同时从1和n出发,会在那个点相遇。  2 #include <set>  3 #include <queue>  4 #include <cstdio>  5 #include <vector>  6 #include <cstring>  7 #include <algorithm>  8 using namespace std;  9 typedef long long LL; 10 #define mem(x,y) memset(x, y, sizeof(x)) 11 #define lson l,m,rt << 1 12 #define rson m+1,r,rt << 1 | 1 13 int gcd(int a,int b){return b == 0 ? a : gcd(b, a % b);} 14 int lcm(int a,int b){return a / gcd(a, b) * b;} 15  16 int T, n, m, Case; 17 LL ans; 18 const int maxn_v = 1e5 + 5; 19 const LL INF = 1e18; 20  21 const int ssize = 2e6 + 1e5 + 5; 22 LL d1[ssize], d2[ssize]; 23  24 struct edge 25 { 26     int to; 27     LL co; 28     edge(int tt, LL cc):to(tt), co(cc){} 29     bool operator < (const edge &other)const 30     { 31         return co > other.co; 32     } 33 }; 34 vector<edge>G[ssize]; 35 void init() 36 { 37     for(int i = 1; i <= n + 2 * m; i++) G[i].clear(); 38     ans = INF; 39 } 40 void dijkstra(int s, LL dis[]) 41 { 42     for(int i = 1; i <= n + 2 * m; i++) dis[i] = INF; 43     priority_queue<edge>que; 44     dis[s] = 0; 45     que.push(edge(s, dis[s])); 46     while(!que.empty()) 47     { 48         edge p = que.top();que.pop(); 49         int v = p.to; 50         if(dis[v] < p.co) continue; 51         for(int i = 0; i < G[v].size(); i++) 52         { 53             edge e = G[v][i]; 54             if(dis[e.to] > dis[v] + e.co) 55             { 56                 dis[e.to] = dis[v] + e.co; 57                 que.push(edge(e.to, dis[e.to])); 58             } 59         } 60     } 61 } 62  63 void solve() 64 { 65     dijkstra(1, d1); 66     dijkstra(n, d2); 67     ans = INF; 68     for(int i = 1; i <= n; i++) 69     { 70         ans = min(ans, max(d1[i], d2[i])); 71     } 72     printf("Case #%d: ", Case); 73  74     if(ans == INF) 75         printf("Evil John\n"); 76     else 77     { 78         printf("%I64d\n", ans); 79         int cnt = 0; 80         for(int i = 1; i <= n; i++) 81         { 82             if(ans == max(d1[i], d2[i])) cnt++; 83         } 84         for(int i = 1; i <= n; i++) 85         { 86             if(ans == max(d1[i], d2[i])) cnt--, printf("%d%c", i, cnt ?   : \n ); 87         } 88     } 89 } 90  91  92 int main() 93 { 94     scanf("%d", &T); 95     for(Case = 1; Case <= T; Case++) 96     { 97         scanf("%d%d", &n, &m); 98         init(); 99         for(int i = 1; i <= m; i++)100         {101             int w, num;102             int s = n + i, e = n + i + m;103             scanf("%d%d", &w, &num);104             G[s].push_back(edge(e, w));105             while(num--)106             {107                 int x;108                 scanf("%d", &x);109                 G[e].push_back(edge(x, 0));110                 G[x].push_back(edge(s, 0));111             }112         }113         solve();114     }115     return 0;116 }

 

2015ACM/ICPC亚洲区沈阳站