分类 - 题解

2018-05-01 23:32:05    180    0    0

A.

  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <map>
  7. #include <queue>
  8. #include <set>
  9. #include <stack>
  10. #include <string>
  11. #define mset(a) memset((a), 0, sizeof(a))
  12. using namespace std;
  13. const int inf = 0x7f7f7f7f;
  14. int main() {
  15. // freopen("input","r",stdin);
  16. int n, s, h, m;
  17. cin >> n >> s;
  18. int last = 0, cur;
  19. for (int i = 1; i <= n; ++i) {
  20. cin >> h >> m;
  21. cur = h * 60 + m;
  22. if (i == 1) {
  23. if (cur - last >= s + 1) {
  24. cout << "0 0" << endl;
  25. return 0;
  26. }
  27. } else {
  28. if (cur - last >= s * 2 + 2) {
  29. cout << (last + s + 1) / 60 << ' ' << (last + s + 1) % 60
  30. << endl;
  31. return 0;
  32. }
  33. }
  34. last = cur;
  35. }
  36. cout << (cur + s + 1) / 60 << ' ' << (cur + s + 1) % 60 << endl;
  37. return 0;
  38. }

B.

  1. #include <algorithm>
  2. #include <cmath
2017-04-06 09:42:34    142    0    0

已AC 4

#31. 【UR #2】猪猪侠再战括号序列

很巧妙的一道题
不妨把括号序列调整成显然合法的情况:(((())))
从左遍历到中点,每次找到一个不是'('的,就在它的右侧找第一个是'('的,然后中间夹着的肯定是一堆')',直接交换两端即可,而且右侧'('的位置一定越来越靠右,所以每次在上一次的基础上找即可
O(n)

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<vector>
  4. using namespace std;
  5. const int maxn = 200005;
  6. char a[maxn];
  7. vector<pair<int,int> > ans;
  8. int main(){
  9. scanf("%s",a);
  10. int l = 0,r = 0,n = strlen(a)/2;
  11. for(;l<n;++l){
  12. if(a[l]=='(')continue;
  13. if(!r)r = l+1;
  14. for(;a[r]!='(';++r);
  15. swap(a[l],a[r]);
  16. ans.push_back(make_pair(l,r));
  17. }
  18. printf("%d\n",ans.size());
  19. for(int i = 0,lim = ans.size();i<lim;++i)
  20. printf("%d %d\n",ans[i].first+1,ans[i].second+1);
  21. return 0;
  22. }

#48. 【UR #3】核聚变反应强度

很好玩的一道题
预处理a1的所有质因子

2017-04-05 08:47:20    92    0    0
构造AC自动机, 计数的转移是矩阵乘法形式, 快速幂加速. * 坑点: 1. poj特慢, 以致于你某个式子模两次会tle, 模一次就ac 2. 构造fail边时不要忘了转移匹配节点的关系! ``` #include #include #include #include #include #include #include #include #include
2017-04-04 16:39:55    121    0    0

python太慢了啊,tle救不过来

  1. def calculate(s,a):
  2. return eval(s)
  3. t = raw_input().replace('^','**')
  4. n = int(raw_input())
  5. s = []
  6. for i in range(0,n):
  7. s.append(raw_input().replace('^','**'))
  8. correct = [1]*n
  9. aes = [233,499,379,239,277,1096,15532]
  10. for a in aes:
  11. ans = calculate(t,a)
  12. for i in range(0,n):
  13. if calculate(s[i],a)!=ans :correct[i] = 0
  14. ans = ''
  15. for i in range(0,n):
  16. if correct[i]==1 : ans += (chr(ord('A')+i))
  17. print ans
2017-04-04 15:43:54    143    0    0

首先sort一下,最小的k个城市我们都不要,然后对后2k个城市无限random_shuffle,直到有解
太暴力啦

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<set>
  7. #include<map>
  8. #include<vector>
  9. #include<stack>
  10. #include<queue>
  11. #define scan(a) scanf("%d",&a)
  12. #define mset(a,b) memset(a,(b),sizeof(a))
  13. using namespace std;
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. const int inf = 0x3f3f3f3f;
  17. const int maxn = 3*60+5;
  18. struct people{
  19. int w,id;
  20. }c[maxn],a[maxn],b[maxn],d[maxn];
  21. bool cmp1(people a,people b){
  22. return a.w<b.w;
  23. }
  24. int ans1[maxn],ans2[maxn],ans3[maxn];
  25. typedef double db;
  26. int main(){
  27. int k;
  28. scan(k);
  29. for(int i = 1;i<=3*k;++i)scan(c[i].w),c[i].id
2017-04-04 11:39:39    103    0    0

ans=i=1nn%i=i=1n(nni)=n2i=1nni

分块计算即可,注意n<=1012,要到处模来模去防止溢出!!

  1. #include<cstdio>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll mod = 1000000007;
  5. int main(){
  6. ll n,inv = (-mod/2+mod)%mod;
  7. scanf("%lld",&n);
  8. ll ans = 0;
  9. for(ll i = 1,last;i<=n;i = last+1){
  10. last = n/(n/i);
  11. ans = (ans+(n/i%mod)*((i+last)%mod)%mod*((last-i+1)%mod)%mod*inv%mod)%mod;
  12. }
  13. printf("%lld\n",(((n%mod)*(n%mod)%mod-ans)%mod+mod)%mod);
  14. }
2017-04-04 10:47:34    94    0    0

如果没有gcd(x,y)=1的限制。
那么我们可以直接将所有abx全部存进一个数组里。
然后将所有bay出现的次数统计进答案里就可以了。
有了限制考虑容斥原理

ans=[1|gcd(x,y)][p|gcd(x,y)]+[pq|gcd(x,y)]+...

即所有数对减有一个公因子,加有两个不同的公因子,减有三个不同公因子...
前面的系数就是μ(),于是我们预处理μ,然后枚举公因子统计答案即可
2017-04-03 19:39:40    383    0    0

给出三个N*N的矩阵A, B, C,问A * B是否等于C?

首先这题比原题数据范围小, O(n3)暴力
原题数据范围是N103, 暴力已经不行了
但我们有随机算法!
假设有AB=C
那我们有M(AB)=MC
又因为结合律(MA)B=MC
然后因为两矩阵P,Q相乘的条件是P的列数等于Q的行数,答案矩阵行数等于P, 列数等于Q
所以我们可以取一个行矩阵M, 来将矩阵乘法复杂度降到n2, 为了提高准确度多随机几个即可。
矩阵乘法打错!!!???

  1. //random
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<cstdlib>
  7. #include<ctime>
  8. using namespace std;
  9. typedef long long ll;
  10. const int maxn = 505;
  11. int n;
  12. struct matrix{
  13. int m[maxn][maxn];
  14. matrix(){
  15. memset(m,0,sizeof(m));
  16. }
  17. };
  18. matrix operator * (matrix a,matrix b){
  19. matrix ret;
  20. for(int i = 1;i<=n;++i)
  21. for(int j = 1;j<=n;++j)
  22. ret.m[1][j] += a.m[1][i]*b.m[i][j];
  23. return ret;
  24. }
  25. bool operator == (matrix a,matrix b){
  26. for(int j = 1;j<=n;++j)
  27. if(a.m[1][j]!=b.m[1][j])return false;
  28. return true;
  29. }
  30. inline int init(){
  31. int x = 0;
  32. char c = getchar();
  33. while(!isdigit(c))
2017-04-04 09:09:00    125    0    0

很巧妙的一个题。
对于一个手机计算一个全是"&&"的表达式,且有afork(),可以知道n(0)=a, n(1)=1.
按"||"把表达式分成好几段只含"&&"的表达式,分别计算并合并。
最初我想了个dfs一遍表达式树统计答案,太难写了..

  1. //分段
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<cmath>
  7. #include<set>
  8. #include<map>
  9. #include<vector>
  10. #include<stack>
  11. #include<queue>
  12. #define scan(a) scanf("%d",&a)
  13. #define mset(a,b) memset(a,(b),sizeof(a))
  14. using namespace std;
  15. typedef long long ll;
  16. typedef unsigned long long ull;
  17. const int inf = 0x3f3f3f3f;
  18. const int maxn = 100005;
  19. const int mod = 998244353;
  20. int n,a[maxn],ans0,ans1,m;
  21. char s[5];
  22. int main(){
  23. scan(n);n--,m = 1;
  24. for(int i = 1;i<=n;++i){
  25. scanf("%s
2017-04-03 21:22:00    192    0    0

有一些人,你需要把他们均分两组(人数差不超过1),且体重差最小

先随机分两组,然后随机交换100次能使答案最优就更新
POJ不支持SRAND!!!!!RE了半小时!!!

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<set>
  7. #include<map>
  8. #include<vector>
  9. #include<stack>
  10. #include<queue>
  11. #include<ctime>
  12. #include<cstdlib>
  13. #define scan(a) scanf("%d",&a)
  14. #define mset(a,b) memset(a,(b),sizeof(a))
  15. using namespace std;
  16. typedef long long ll;
  17. typedef unsigned long long ull;
  18. const int inf = 0x3f3f3f3f;
  19. const int maxn = 1000005;
  20. vector<int> a;
  21. int b[maxn],c[maxn],n;
  22. int main(){
  23. //srand(time(0));
  24. cin>>n;
  25. for(int i = 0;i<n;++i){
  26. int t;
  27. cin>>t;
  28. a.push_back(t);
  29. }
  30. if(n==1){
  31. printf("0 %d\n",a[0]);
  32. return 0;
  33. }
  34. int l = n/2,r = n-l,T = 0,ansl = -inf,ansr = inf;
  35. while(T++<300){
  36. int sl = 0,sr = 0,cnt = 0;
  37. random_shu