寒假第二周 1.18 --- 1.24

104 阅读 0 评论 69 点赞

我是靠谱客的博主友好钢笔，最近开发中收集的这篇文章主要介绍寒假第二周 1.18 --- 1.24，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.18

cf 581c

581C - Developing Skills

重新自己写了一遍，注意都是0 的时候

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 const int maxn = 1e5+5;
 9 int n,k;
10
11 struct node{
12
int x,y;
13 }p[maxn];
14
15 int cmp(node n1,node n2){
16
return n1.y < n2.y;
17 }
18
19 int cmp0(node n1,node n2){
20
return n1.x < n2.x;
21 }
22
23 int a[105];
24
25 void solve(){
26
for(int i = 1;i <= n;i++){
27
int pos = lower_bound(a+1,a+10,p[i].x) - a;
28
if(a[pos] == p[i].x) pos++;
29
p[i].y = a[pos] - p[i].x;
30
//
printf("a[%d] = %d
p[%d].x = %dn",pos,a[pos],i,p[i].x);
31 
}
32
/* for(int i = 1;i <= n;i++){
33 
printf("p[%d].x = %d
y = %dn",i,p[i].x,p[i].y);
34 
}*/
35
sort(p+1,p+n+1,cmp);
36
int ans = 0;
37
for(int i = 1;i <= n;i++){
38
if(k >= p[i].y){
39
ans += (p[i].x + p[i].y)/10;
40
k -= p[i].y;
41
p[i].x = p[i].x + p[i].y;
42 
}
43
else {
44
ans += p[i].x/10;
45 
}
46
// printf("i = %d
k = %d
ans = %dn",i,k,ans);
47 
}
48
if(k){
49
for(int i = 1;i <= n;i++){
50
int l = 10 - p[i].x/10;
51
int r = k/10;
52
if(r >= l){
53
ans += l;
54
k = k-l*10;
55 
}
56
else{
57
ans += k/10;
58
k = k%10;
59 
}
60
if(k < 10) break;
61
//printf("l = %d
r = %d
k = %n",l,r,k);
62 
}
63 
}
64
printf("%dn",ans);
65 }
66
67 int main(){
68
for(int i = 1;i <= 10;i++) a[i] = i*10;
69
a[11] = 100;
70
//
freopen("in.txt","r",stdin);
71
// freopen("out.txt","w",stdout);
72
while(scanf("%d %d",&n,&k) != EOF){
73
for(int i = 1;i <= n;i++){
74
scanf("%d",&p[i].x);
75 
}
76 
solve();
77 
}
78
return 0;
79 }

View Code

cf 614e

614E - Necklace

先不理解题解说的 part 是什么意思，，就是所有a[i] 的gcd

然后像题解说的那样构造


1 #include<cstdio>

2 #include<cstring>

3 #include<vector>

4 #include<iostream>

5 #include<algorithm>

6 using namespace std;

7

8 const int maxn = 1e5+5;

9 char s[maxn];
 10 int n,a[maxn],aa[maxn];
 11
 12 int gcd(int a,int b){
 13
return (!b) ? a:gcd(b,a%b);
 14 }
 15
 16 void solve(){
 17
int part = a[1];
 18
for(int i = 2;i <= n;i++){
 19
part = gcd(part,a[i]);
 20 
}
 21
for(int i = 1;i <= n;i++){
 22
aa[i] = a[i]/part;
 23 
}
 24
 25
if(part%2 == 0){
 26
printf("%dn",part);
 27
vector<char> c;
 28
for(int i = 1;i <= n;i++){
 29
for(int j = 1;j <= aa[i];j++){
 30
c.push_back(i+'a'-1);
 31 
}
 32 
}
 33
int flag = 1;
 34
for(int i = 1;i <= part;i++){
 35
if(flag){
 36
for(int j = 0;j < c.size();j++){
 37
printf("%c",c[j]);
 38 
}
 39 
}
 40
else{
 41
for(int j = c.size()-1;j >= 0;j--){
 42
printf("%c",c[j]);
 43 
}
 44 
}
 45
flag = !flag;
 46 
}
 47
printf("n");
 48
return;
 49 
}
 50
int ji = 0;
 51
for(int i = 1;i <= n;i++){
 52
ji += (aa[i]%2);
 53 
}
 54
if(ji > 1){
 55
puts("0");
 56
for(int i = 1;i <= n;i++){
 57
for(int j = 1;j <= a[i];j++){
 58
char z = i+'a'-1;
 59
printf("%c",z);
 60 
}
 61 
}
 62
printf("n");
 63 
}
 64
if(ji == 1){
 65
vector<char> l;
 66
vector<char> r;
 67
int pos;
 68
for(int i = 1;i <= n;i++){
 69
if(a[i]%2){
 70
pos = i;
 71
break;
 72 
}
 73 
}
 74
for(int i = 1;i <= n;i++){
 75
if(i == pos) continue;
 76
for(int j = 1;j <= aa[i]/2;j++){
 77
l.push_back(i+'a'-1);
 78
r.push_back(i+'a'-1);
 79 
}
 80 
}
 81
for(int j = 1;j <= aa[pos];j++){
 82
l.push_back(pos+'a'-1);
 83 
}
 84 
reverse(r.begin(),r.end());
 85
for(int j = 0;j < r.size();j++){
 86 
l.push_back(r[j]);
 87 
}
 88
printf("%dn",part);
 89
for(int i = 1;i <= part;i++){
 90
for(int j = 0;j < l.size();j++){
 91
printf("%c",l[j]);
 92 
}
 93 
}
 94
printf("n");
 95 
}
 96 }
 97
 98 int main(){
 99
while(scanf("%d",&n) != EOF){
100
for(int i = 1;i <= n;i++){
101
scanf("%d",&a[i]);
102 
}
103 
solve();
104 
}
105
return 0;
106 }

View Code

hdu 1069

加了一维的 dag 上的动规，去年的时候就在紫薯上看，不会写- -

然后，sb的我是这样的，用 g[i][j][k][z] 建图，表示第 i 个立方体的第k 面为底面的时候，能够放在第 j 个立方体的第z面为底面的时候

后来不会写了---

-------------------

稍微转化一下就和普通的一样了，就是每个立方体三种放置的情况分别拆成三个立方体，就可以了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 const int maxn = 1005;
 9 int dp[maxn],n;
10
11 struct node{
12
int x,y,z;
13 }p[maxn];
14
15 int dfs(int i){
16
if(dp[i]) return dp[i];
17
int ans = 0;
18
for(int j = 1;j <= 3*n;j++){
19
if(p[j].x > p[i].x && p[j].y > p[i].y){
20
ans = max(ans,dfs(j));
21 
}
22 
}
23
return dp[i] = ans + p[i].z;
24 }
25
26 int main(){
27
int kase = 0;
28
while(scanf("%d",&n) != EOF){
29
if(n == 0) break;
30
int a[5];
31
int cnt = 0;
32
for(int i = 1;i <= n;i++){
33
scanf("%d %d %d",&a[0],&a[1],&a[2]);
34
sort(a,a+3);
35
p[++cnt].x = a[0];p[cnt].y = a[1];p[cnt].z = a[2];
36
p[++cnt].x = a[1];p[cnt].y = a[2];p[cnt].z = a[0];
37
p[++cnt].x = a[0];p[cnt].y = a[2];p[cnt].z = a[1];
38 
}
39
int res = -1;
40
memset(dp,0,sizeof(dp));
41
for(int i = 1;i <= 3*n;i++){
42
res = max(res,dfs(i));
43 
}
44
printf("Case %d: maximum height = %dn",++kase,res);
45 
}
46
return 0;
47 }

View Code

hdu 1087

最大的严格上升的序列的和

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6
 7 typedef long long LL;
 8 const int maxn = 1005;
 9 int n,a[maxn];
10 LL dp[maxn];
11
12 void solve(){
13
memset(dp,0,sizeof(dp));
14
a[0] = 0;
15
for(int i = 1;i <= n;i++){
16
for(int j = 1;j < i;j++){
17
if(a[i] > a[j]){
18
dp[i] = max(dp[i],dp[j]+1LL*a[i]);
19 
}
20 
}
21
dp[i] = max(dp[i],1LL*a[i]);
22
// printf("dp[%d] = %dn",i,dp[i]);
23 
}
24
LL ans = -1;
25
for(int i = 1;i <= n;i++){
26
ans = max(ans,dp[i]);
27 
}
28
printf("%I64dn",ans);
29 }
30
31 int main(){
32
while(scanf("%d",&n) != EOF){
33
if(n == 0) break;
34
for(int i = 1;i <= n;i++){
35
scanf("%d",&a[i]);
36 
}
37 
solve();
38 
}
39
return 0;
40 }
41
42 FAQ | About Virtual Judge | Forum | Discuss | Open Source Project
43 All Copyright Reserved ©2010-2014 HUST ACM/ICPC TEAM
44 Anything about the OJ, please ask in the forum, or contact author:Isun
45 Server Time: 2016-01-19 22:29:09

View Code

hdu 1114

完全背包必须装满的最优解

dp[0] 初始化为 0 ，其余容量初始化为无穷大

---话说就搜了下完全背包必须装满，题解都出来了-----

，只有初始容量为0价值为 0 的包装满才是合法的解，

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6
 7 typedef long long LL;
 8 const int INF = (1<<30)-1;
 9 const int maxn = 10005;
10 int w[maxn],v[maxn],n,e,f,V;
11 int dp[maxn];
12
13 void solve(){
14
dp[0] = 0;
15
V = f-e;
16
for(int i = 1;i <= V;i++) dp[i] = INF;
17
for(int i = 1;i <= n;i++){
18
for(int j = w[i];j <= V;j++){
19
dp[j] = min(dp[j-w[i]]+v[i],dp[j]);
20
//
printf("dp[%d] = %dn",j,dp[j]);
21 
}
22 
}
23
if(dp[V] == INF) puts("This is impossible.");
24
else printf("The minimum amount of money in the piggy-bank is %d.n",dp[V]);
25 }
26
27 int main(){
28
int T;
29
scanf("%d",&T);
30
while(T--){
31
scanf("%d %d",&e,&f);
32
scanf("%d",&n);
33
for(int i = 1;i <= n;i++){
34
scanf("%d %d",&v[i],&w[i]);
35 
}
36 
solve();
37 
}
38
return 0;
39 }

View Code

1.19

hdu 1176

数塔

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6
 7 const int maxn = 1e5+5;
 8 int dp[maxn][15],a[maxn][15];
 9 int n,T;
10
11 void solve(){
12
memset(dp,0,sizeof(dp));
13
for(int i = T;i >= 0;i--){
14
dp[i][0] = max(dp[i+1][0],dp[i+1][1]) + a[i][0];
15
//
printf("dp[%d][0] = %dn",i,dp[i][0]);
16
for(int j = 1;j <= 9;j++){
17
dp[i][j] = max(max(dp[i+1][j-1],dp[i+1][j+1]),dp[i+1][j]) + a[i][j];
18
//
printf("dp[%d][%d] = %dn",i,j,dp[i][j]);
19 
}
20
dp[i][10] = max(dp[i+1][10],dp[i+1][9]) + a[i][10];
21
// printf("dp[%d][10] = %dn",i,dp[i][10]);
22 
}
23
printf("%dn",dp[0][5]);
24 }
25
26 int main(){
27
while(scanf("%d",&n) != EOF){
28
if(n == 0) break;
29
memset(a,0,sizeof(a));
30
int x,t;
31
T = -1;
32
for(int i = 1;i <= n;i++){
33
scanf("%d %d",&x,&t);
34
a[t][x]++;
35
T = max(T,t);
36 
}
37 
solve();
38 
}
39
return 0;
40 }

View Code

hdu 1260

...燃烧生命wa 水题.....

输出的时间最大是 12

-----一直纳闷---我有%12阿

-------

12:00:00 是 am（还要再判断下分钟和秒钟---sad---）

然后再多一点点就是 pm 了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 const int maxn = 5005;
 9 int dp[maxn],a[maxn],b[maxn];
10 int n;
11 const int INF = (1<<30)-1;
12
13 void solve(){
14
for(int i = 1;i < maxn;i++) dp[i] = INF;
15
dp[0] = 0;
16
for(int i = 1;i <= n;i++){
17
if(i == 1){
18
dp[i] = a[i];
19 
}
20
if(i >= 2){
21
dp[i] = min(dp[i-1]+a[i],dp[i-2]+b[i-1]);
22 
}
23
// printf("dp[%d] = %dn",i,dp[i]);
24 
}
25
int shi = dp[n]/3600;
26
int fen = (dp[n]-shi*3600)/60;
27
int miao = dp[n] - shi*3600-fen*60;
28
char c1,c2;
29
shi = shi+8;
30
if(shi < 12||shi == 12 && fen == 0 && miao == 0){
31
c1 = 'a';
32
c2 = 'm';
33 
}
34
else{
35
if(shi != 12) shi %= 12;
36
c1 = 'p';
37
c2 = 'm';
38 
}
39
// printf("shi = %d
fen = %d
miao = %dn",shi,fen,miao);
40
printf("%02d:%02d:%02d %c%cn",shi,fen,miao,c1,c2);
41 }
42
43 int main(){
44
int T;
45
scanf("%d",&T);
46
while(T--){
47
scanf("%d",&n);
48
for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
49
for(int i = 1;i <= n-1;i++) scanf("%d",&b[i]);
50 
solve();
51 
}
52
return 0;
53 }

View Code

cf 602 d 602D - Lipshitz Sequence

b[i] = abs(a[i] - a[i-1]) ，求出每个b[i] 作为最大值的时候，向左能延伸多远，向右能延伸多远

---话说是看的题解补的题---

然后因为两个地方没有注意到，代码一直不对，

就是比如现在的询问是 [l,r]

b[l] 是 a[l] 与 a[l-1] 的差值，不包含在这个区间里面，所以应该 l++;

还有就是递推 left[]，right[] 数组的时候，只需要一个是 >= ，免得把区间算重了--

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7
 8 const int maxn = 1e6+5;
 9 typedef long long LL;
10 int n,l[maxn],r[maxn];
11 int a[maxn],b[maxn];
12 int q;
13
14 void solve(){
15
memset(b,0,sizeof(b));
16
memset(l,0,sizeof(l));
17
memset(r,0,sizeof(r));
18
for(int i = 2;i <= n;i++){
19
b[i] = abs(a[i] - a[i-1]);
20 
}
21
22
/*
for(int i = 2;i <= n;i++){
23 
printf("%d ",b[i]);
24 
}
25 
printf("n");*/
26
27
for(int i = 1;i <= q;i++){
28
int lb,ub;
29
scanf("%d %d",&lb,&ub);
30
lb++;
31
for(int j = lb;j <= ub;j++){
32
l[j] = j;
33
r[j] = j;
34 
}
35
for(int j = lb;j <= ub;j++){
36
while(l[j] > lb && b[j] > b[l[j]-1]){
37
l[j] = l[l[j]-1];
38 
}
39 
}
40
for(int j = ub;j >= lb;j--){
41
while(r[j] < ub && b[j] >= b[r[j]+1]){
42
r[j] = r[r[j]+1];
43 
}
44 
}
45
LL ans = 0;
46
for(int j = lb;j <= ub;j++){
47
LL cnt = (1LL*(r[j]-j+1)*(j-l[j]+1));
48
//
printf("l[%d] = %d
r[%d] = %d
cnt = %I64d
b[%d] = %dn",j,l[j],j,r[j],cnt,j,b[j]);
49
ans += cnt*b[j];
50 
}
51
printf("%I64dn",ans);
52 
}
53 }
54
55 int main(){
56
while(scanf("%d %d",&n,&q) != EOF){
57
for(int i = 1;i <= n;i++){
58
scanf("%d",&a[i]);
59 
}
60 
solve();
61 
}
62
return 0;
63 }

View Code

cf 584e 584E - Anton and Ira

重新做以前的题，还是不会捉了----sad---

交换的方法就是 : 如果当前的 p[i] 和 s[i] 不同，那么就在 p[] 里面找到 p[ed] = s[i]

然后，在 p[i] 到 p[ed] 中，如果存在 p[x],这个p[x] 在 s 中的位置大于 ed，就交换 ed 和 x

直到换到 ed = i

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 typedef long long LL;
 9 typedef pair<int,int> pii;
10 const int maxn = 1e5+5;
11 int p[maxn],s[maxn];
12 int n;
13 int pos[maxn];
14
15 void solve(){
16
vector<pii> ans;
17
LL res = 0;
18
int st = 0,ed = 0;
19
for(int i = 1;i <= n;i++){
20
ed = 0;
21
if(p[i] == s[i]) continue;
22
for(int j = 1;j <= n;j++){
23
if(p[j] == s[i]){
24
ed = j;
25
break;
26 
}
27 
}
28
//
printf("---i = %d
ed = %dn",i,ed);
29
while(ed != i){
30
for(int j = i;j < ed;j++){
31
if(pos[p[j]] >= ed){
32 
swap(ed,j);
33 
swap(p[ed],p[j]);
34
//
printf("=== ed = %d
j = %dn",ed,j);
35
res += 1LL*abs(ed-j);
36 
ans.push_back(make_pair(ed,j));
37
break;
38 
}
39 
}
40 
}
41 
}
42
printf("%I64dn",res);
43
printf("%dn",ans.size());
44
for(int i = 0;i < ans.size();i++){
45
printf("%d %dn",ans[i].first,ans[i].second);
46 
}
47 }
48
49 int main(){
50
while(scanf("%d",&n) != EOF){
51
for(int i = 1;i <= n;i++) scanf("%d",&p[i]);
52
for(int i = 1;i <= n;i++) {
53
scanf("%d",&s[i]);
54
pos[s[i]] = i;
55 
}
56 
solve();
57 
}
58
return 0;
59 }

View Code

cf 584b 584B - Kolya and Tanya

当时做这场比赛的时候，，，一看到推公式，，，就跑到oeis 搜---

什么都没搜到----gg---

稍微推一下，就是 3^3n - 7^n

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6
 7 typedef long long LL;
 8 const int mod = 1e9+7;
 9 int n;
10
11 LL Q_pow(LL x,LL y){
12
LL res = 1;
13
x %= mod;
14
while(y){
15
if(y&1) res = res*x%mod;
16
x = x*x%mod;
17
y >>= 1;
18 
}
19
return res;
20 }
21
22 void solve(){
23
LL ans = (Q_pow(3,3*n) - Q_pow(7,n)+mod)%mod;
24
printf("%I64dn",ans);
25 }
26
27 int main(){
28
while(scanf("%d",&n) != EOF){
29 
solve();
30 
}
31
return 0;
32 }

View Code

1.20

寒假起床最晚的一次 T_T

补---题---

cf 496b 496B - Secret Combination

暴力枚举

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 const int maxn = 1e5+5;
 9 int n;
10 char s[maxn],t[maxn];
11 char p[10][maxn];
12
13 void solve(){
14
vector<string> c;
15
16
for(int i = 0;i <= 9;i++){
17
for(int j = 1;j <= n;j++){
18
p[i][j] = ((s[j]-'0')+i)%10+'0';
19 
}
20 
}
21
22
/*
for(int i = 0;i <= 9;i++){
23 
printf("i = %d
p = %sn",i,p[i]+1);
24 
}*/
25
26
27
for(int i = 0;i <= 9;i++){
28
for(int k = 0;k <= n-1;k++){
29
int cnt = 0;
30
for(int l = k+1;l <= n;l++){
31
t[++cnt] = p[i][l];
32 
}
33
for(int l = 1;l <= k;l++){
34
t[++cnt] = p[i][l];
35 
}
36
//
printf("i = %d
k = %d
t = %sn",i,k,t+1);
37
c.push_back(t+1);
38 
}
39 
}
40 
sort(c.begin(),c.end());
41
printf("%sn",c[0].c_str());
42 }
43
44 int main(){
45
while(scanf("%d",&n) != EOF){
46
scanf("%s",s+1);
47 
solve();
48 
}
49
return 0;
50 }

View Code

cf 496c 496C - Removing Columns

....燃烧生命wa水题....sad---

.....wa 了好久....好久....好久阿

给出 n*m 的字母矩阵，为了使得从上到下是字典序递增，至少需要删掉多少列（不是严格递增）

直接判断每一列是不是必须删掉

如果这一列是严格上升的，那就不用管

如果这一列出现了s[i][j] < s[i][j-1] ，就必须删掉

如果这一列是非严格上升的，就用 vector 把相同的[st,ed] 存起来，下次就只需要再判断vector 里面的了---

一直 wa 是因为，当判断到这一列必须删掉的时候，，，还把这一列后面的[st,ed] 丢进了 vector里面

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 typedef pair<int,int> pii;
 9 char s[105][105];
10 int n,m;
11 int lie;
12
13 int check(int st,int ed){
14
int flag = 0;
15
for(int j = st;j <= ed;j++){
16
if(j == st) continue;
17
if(s[j][lie] < s[j-1][lie]) return 0;
18
if(s[j][lie] == s[j-1][lie]) flag = 1;
19
20 
}
21
if(flag == 1) return 2;
22
return 1;
23 }
24
25 void solve(){
26
if(n == 1){
27
puts("0");
28
return;
29 
}
30
int res = 0;
31
vector<pii> c[3];
32
lie = 1;
33
int l = 1,r = n;
34
c[0].push_back(make_pair(l,r));
35
int key = 0;
36
int tot = 0;
37
while(1){
38
int cnt = 0;
39
int lb = 0,ub = 0;
40
for(int i = 0;i < c[key].size();i++){
41
int x = c[key][i].first;
42
int y = c[key][i].second;
43
// printf("i = %d
res = %d lie = %d x = %d
y = %dn",i,res,lie,x,y);
44
if(check(x,y) == 1) cnt++;
45
if(check(x,y) == 0){
46
lb = 1;
47 
}
48
if(check(x,y) == 2){
49
ub = 1;
50 
}
51 
}
52
//printf("---cnt = %dn",cnt);
53
if(cnt == c[key].size()) break;
54
if(lb){
55
res++;
56
c[1-key] = c[key];
57 
}
58
else{
59
for(int i = 0;i < c[key].size();i++){
60
int x = c[key][i].first;
61
int y = c[key][i].second;
62
//
printf("i = %d
res = %d lie = %d x = %d
y = %dn",i,res,lie,x,y);
63
if(check(x,y) == 1) continue;
64
if(check(x,y) == 2){
65
for(int p = x;p <= y;){
66
int q = p;
67
while(q<=y && s[q][lie] == s[p][lie])q++;
68
if(q-p > 1){
69
c[1-key].push_back(make_pair(p,q-1));
70 
}
71
p = q;
72 
}
73 
}
74 
}
75 
}
76 
c[key].clear();
77
key = !key;
78
lie++;
79
if(lie == m+1) break;
80 
}
81
printf("%dn",res);
82 }
83
84 int main(){
85
while(scanf("%d %d",&n,&m) != EOF){
86
for(int i = 1;i <= n;i++){
87
scanf("%s",s[i]+1);
88 
}
89 
solve();
90 
}
91
return 0;
92 }

View Code

搜了下题解，，发现自己的做法sb爆了阿

可以用一个数组c[]标记已经不需要再管的行，然后每次碰到一列如果存在下降的情况，就删掉

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 int n,m;
 9 char s[105][105];
10
11 void solve(){
12
int c[105];
13
memset(c,0,sizeof(c));
14
int ans = 0;
15
16
if(n == 1){
17
puts("0");
18
return;
19 
}
20
for(int i = 1;i <= m;i++){
21
int ok = 0;
22
for(int j = 2;j <= n;j++){
23
if(c[j]) continue;
24
if(s[j][i] < s[j-1][i]){
25
ok = 1;
26
break;
27 
}
28 
}
29
if(ok){
30
ans++;
31 
}
32
else{
33
for(int j=2;j <= n;j++){
34
if(s[j][i] > s[j-1][i]){
35
c[j] = 1;
36 
}
37 
}
38 
}
39 
}
40
printf("%dn",ans);
41 }
42
43 int main(){
44
while(scanf("%d %d",&n,&m) != EOF){
45
for(int i = 1;i <= n;i++){
46
scanf("%s",s[i]+1);
47 
}
48 
solve();
49 
}
50
return 0;
51 }

View Code

1.21

cf 577b Modulo Sum

不会做的题就再补一次叭--

n > m 的时候，由鸽巢原理

sum[i] 为前 i 项的和对 m 取模

有n 个sum[i] 需要放到 m 个盒子里面，所以肯定有一个盒子里面放了2个sum[i]

所以一定存在 sum[l] = sum[r]

在区间 [l+1,r] 就满足了

然后 n <= m 的时候就dp一下

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<set>
 6 using namespace std;
 7
 8 const int maxn = 1e6+5;
 9 int dp[2][maxn],n,m;
10 int a[maxn];
11 int sum[maxn];
12
13 void solve(){
14
memset(dp,0,sizeof(dp));
15
if(n <= m){
16
int key = 0;
17
for(int i = 1;i <= n;i++){
18
dp[key][a[i]%m] = 1;
19
for(int j = 0;j < m;j++){
20
if(dp[1-key][j]){
21
dp[key][(j+a[i])%m] = 1;
22 
}
23 
}
24
for(int j = 0;j < m;j++) dp[1-key][j] = dp[key][j];
25
key = !key;
26 
}
27
if(dp[key][0]) puts("YES");
28
else puts("NO");
29
return;
30 
}
31
memset(sum,0,sizeof(sum));
32
for(int i = 1;i <= n;i++){
33
sum[i] = (sum[i-1]+a[i])%m;
34 
}
35
set<int> s;
36
for(int i = 1;i <= n;i++){
37
if(s.count(sum[i]) == 0){
38 
s.insert(sum[i]);
39 
}
40
else{
41
puts("YES");
42
return;
43 
}
44 
}
45
puts("NO");
46 }
47
48 int main(){
49
while(scanf("%d %d",&n,&m) != EOF){
50
for(int i = 1;i <= n;i++){
51
scanf("%d",&a[i]);
52 
}
53 
solve();
54 
}
55
return 0;
56 }

View Code

然后搜鸽巢原理来看的时候，水一道题

hdu 1205

给出 n 种物品，个数分别为 a[i],要将每种物品错开来放，问是否可能

最大的a[i] 共有 a[i] - 1个空隙，只需要看剩下的数够不够填这些空隙

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6
 7 typedef long long LL;
 8 const int maxn = 1e6+5;
 9 int a[maxn];
10 LL sum;
11 int n;
12
13 void solve(){
14
int maxx = -1;
15
sum = 0;
16
for(int i = 1;i <= n;i++){
17
maxx = max(maxx,a[i]);
18
sum += 1LL*a[i];
19 
}
20
if(sum-maxx >= maxx-1) puts("Yes");
21
else puts("No");
22 }
23
24 int main(){
25
int T;
26
scanf("%d",&T);
27
while(T--){
28
scanf("%d",&n);
29
for(int i = 1;i <= n;i++){
30
scanf("%d",&a[i]);
31 
}
32 
solve();
33 
}
34
return 0;
35 }

View Code

cf 496d 496D - Tennis Game

按照时间给出 n 小局比赛的胜负，1 为A赢，2为 B赢，每赢一局得1分

如果一个人赢够了 t 分，那么这一大局比赛结束，如果一个人赢够了 s 大局，整个比赛就结束

求所有合法的s,t

-----先自己想的是枚举t，二分 s，可是不懂判断对应一个 t ，这个s是不是合法---

----然后可以这样

先预处理出sum1[i] 表示前 i 项有多少个1

　　　　　sum2[i]表示前 i 项有多少个2

枚举t,然后直接去计算 s

注意的是，如果一个人这场比赛赢的话，那么最后一小局也是他赢

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 typedef pair<int,int> pii;
 9 const int maxn = 1e5+5;
10 int sum1[maxn],sum2[maxn];
11 int a[maxn],n;
12
13 int work(int t){
14
int pos = 0,p1,p2,s1=0,s2=0,win;
15
while(pos <= n){
16
p1 = lower_bound(sum1+1,sum1+n+1,sum1[pos]+t) - sum1;
17
p2 = lower_bound(sum2+1,sum2+n+1,sum2[pos]+t) - sum2;
18
//
printf("t = %d p1 = %d p2 = %d s1 = %d s2 = %dn",t,p1,p2,s1,s2);
19
if(p1 < p2){
20
s1++;
21
win = 1;
22 
}
23
pos = min(p1,p2);
24
if(p1 > p2){
25
s2++;
26
win = 2;
27 
}
28
if(pos == n) break;
29
if(pos > n) return 0;
30 
}
31
//
printf("-- t= %d win = %d
s1 = %d s2 = %d pos = %dn",t,win,s1,s2,pos);
32
if((win == 1 && s1 > s2 ) || (win == 2 && s1 < s2)) return max(s1,s2);
33
return 0;
34 }
35
36 void solve(){
37
memset(sum1,0,sizeof(sum1));
38
memset(sum2,0,sizeof(sum2));
39
for(int i = 1;i <= n;i++){
40
if(a[i] == 1) sum1[i] = sum1[i-1]+1;
41
else sum1[i] = sum1[i-1];
42
if(a[i] == 2) sum2[i] = sum2[i-1]+1;
43
else sum2[i] = sum2[i-1];
44 
}
45
46
/*for(int i = 1;i <= n;i++){
47 
printf("sum1[%d] = %d
sum2[%d] = %dn",i,sum1[i],i,sum2[i]);
48 
}*/
49
50
vector<pii> ans;
51
for(int i = 1;i <= n;i++){
52
int s = work(i);
53
if(s == 0) continue;
54 
ans.push_back(make_pair(s,i));
55 
}
56 
sort(ans.begin(),ans.end());
57
printf("%dn",ans.size());
58
for(int i = 0;i < ans.size();i++){
59
printf("%d %dn",ans[i].first,ans[i].second);
60 
}
61 }
62
63 int main(){
64
while(scanf("%d",&n) != EOF){
65
for(int i = 1;i <= n;i++){
66
scanf("%d",&a[i]);
67 
}
68 
solve();
69 
}
70
return 0;
71 }

View Code

hdu 1160

找出最长的满足

w[i] < w[i+1] < ---- < w[x]

s[i] > s[i+1] > --- > s[x]

输出长度和路径

想到暑假做的连通分量的缩点之后求DAG上的最长路，

按照关系建好图，dfs一下，找出最大值，再根据这个最大值去找路径


1 #include<cstdio>

2 #include<cstring>

3 #include<iostream>

4 #include<algorithm>

5 #include<vector>

6 using namespace std;

7

8 const int maxn = 1e3+5;

9
 10 struct node{
 11
int x,y;
 12
int id;
 13 }p[maxn];
 14
 15 vector<int> g[maxn];
 16 int n;
 17 int dp[maxn];
 18
 19 int dfs(int u){
 20
if(dp[u]) return dp[u];
 21
for(int i = 0;i < g[u].size();i++){
 22
int v = g[u][i];
 23
dp[u] = max(dp[u],dfs(v));
 24 
}
 25
return dp[u] = dp[u]+1;
 26 }
 27
 28 void solve(){
 29
for(int i = 1;i <= n;i++) g[i].clear();
 30
memset(dp,0,sizeof(dp));
 31
/*
for(int i = 1;i <= n;i++){
 32 
printf("p[%d].x = %d p[%d].y = %dn",i,p[i].x,i,p[i].y);
 33 
}*/
 34
 35
for(int i = 1;i <= n;i++){
 36
for(int j = 1;j <= n;j++){
 37
if(i == j) continue;
 38
if(p[i].x < p[j].x && p[i].y > p[j].y){
 39 
g[i].push_back(j);
 40 
}
 41 
}
 42 
}
 43
 44 /*
for(int i = 1;i <= n;i++){
 45 
printf("---i = %d
",i);
 46 
for(int j = 0;j < g[i].size();j++){
 47 
printf("%d ",g[i][j]);
 48 
}
 49 
printf("n");
 50 
}*/
 51
 52
int res = -1;
 53
for(int i = 1;i <= n;i++){
 54
int tmp = dfs(i);
 55
res = max(res,tmp);
 56
//
printf("i = %d
tmp = %dn",i,tmp);
 57 
}
 58
 59
//
for(int i = 1;i <= n;i++){
 60
//
printf("--dp[%d] = %dn",i,dp[i]);
 61
//}
 62
 63
vector<int> l;
 64
int st = 0,maxx = -1;
 65
for(int i = 1;i <= n;i++){
 66
if(dp[i] > maxx){
 67
st = i;
 68
maxx = dp[i];
 69 
}
 70 
}
 71
int r = res;
 72 
l.push_back(st);
 73
// printf("--st = %dn",st);
 74
while(r>=1){
 75
for(int i = 0;i < g[st].size();i++){
 76
int v = g[st][i];
 77
if(dp[v] == r){
 78
st = v;
 79
//
printf("v = %dn",v);
 80 
l.push_back(v);
 81
break;
 82 
}
 83 
}
 84
r--;
 85 
}
 86
printf("%dn",l.size());
 87
for(int i = 0;i < l.size();i++){
 88
printf("%dn",l[i]);
 89 
}
 90 }
 91
 92 int main(){
 93
//
freopen("in.txt","r",stdin);
 94
//freopen("out.txt","w",stdout);
 95
n = 1;
 96
while(scanf("%d %d",&p[n].x,&p[n].y) != EOF){
 97
n++;
 98 
}
 99 
solve();
100
return 0;
101 }

View Code

cf 495b 495B - Modular Equations

求满足 a %x = b 的x有多少个

a = b 无穷多个

a < b 0个

a > b

可以化简成 a = kx + b

所以 kx = a-b

就在1 到 sqrt(a-b) 之间枚举k,记录答案

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<map>
 7 #include<vector>
 8 using namespace std;
 9
10 int a,b;
11 const int maxn = 1e6+5;
12
13 void solve(){
14
if(a == b){
15
puts("infinity");
16
return;
17 
}
18
if(a < b){
19
puts("0");
20
return;
21 
}
22
int ans = 0;
23
int n=a-b;
24
for(int i = 1;i <= sqrt(n);i++){
25
if(n%i == 0){
26
int x = i;
27
int y = n/i;
28
if(x == y && x > b){
29
ans++;
30
continue;
31 
}
32
if(x > b) {
33
ans++;
34
//
printf("--x = %dn",x);
35 
}
36
if(y > b) {
37
ans++;
38
//
printf("---y = %dn",y);
39 
}
40 
}
41 
}
42
43
printf("%dn",ans);
44 }
45
46 int main(){
47
48
while(scanf("%d %d",&a,&b) != EOF){
49 
solve();
50 
}
51
return 0;
52 }

View Code

cf 495c 495C - Treasure

括号匹配，先消去一次后，再补

每次取s.top()的时候，记得判断下size阿，老是re


1 #include<cstdio>

2 #include<cstring>

3 #include<iostream>

4 #include<algorithm>

5 #include<vector>

6 #include<stack>

7 using namespace std;

8

9 const int maxn = 1e5+5;
 10 char t[maxn];
 11 int n;
 12 int ans[maxn];
 13
 14 void solve(){
 15
n = strlen(t+1);
 16
stack<char> s;
 17
int ub = 0;
 18
for(int i = 1;i <= n;i++){
 19
if(t[i] == '#'){
 20 
s.push(t[i]);
 21
ub++;
 22
continue;
 23 
}
 24
if(t[i] == '('){
 25 
s.push(t[i]);
 26 
}
 27
if(t[i] == ')'){
 28
if(s.size() != 0){
 29
char c = s.top();
 30
int cnt = 0;
 31
while(c == '#'){
 32 
s.pop();
 33
cnt++;
 34
if(s.size() == 0) break;
 35
c = s.top();
 36 
}
 37
//
printf("---cnt = %dn",cnt);
 38
if(c == '(') {
 39 
s.pop();
 40
for(int j = 1;j <= cnt;j++){
 41
s.push('#');
 42 
}
 43 
}
 44
else{
 45
puts("-1");
 46
return;
 47 
}
 48 
}
 49
else{
 50
puts("-1");
 51
return;
 52 
}
 53 
}
 54 
}
 55
vector<char> cp;
 56
while(!s.empty()){
 57 
cp.push_back(s.top());
 58 
s.pop();
 59 
}
 60 
reverse(cp.begin(),cp.end());
 61
/*
for(int i = 0;i < cp.size();i++){
 62 
printf("%c",cp[i]);
 63 
}
 64 
printf("n");*/
 65
 66
int lb = 0;
 67
memset(ans,0,sizeof(ans));
 68
for(int i = 0;i < cp.size();i++){
 69
if(cp[i] == '('){
 70 
s.push(cp[i]);
 71 
}
 72
if(cp[i] == '#'){
 73
if(s.size() == 0){
 74
puts("-1");
 75
return;
 76 
}
 77
lb++;
 78
if(lb != ub){
 79
ans[lb] = 1;
 80 
s.pop();
 81 
}
 82
else{
 83
ans[lb] = s.size();
 84
while(!s.empty()) s.pop();
 85 
}
 86 
}
 87
if(cp[i] == ')'){
 88
puts("-1");
 89
return;
 90 
}
 91 
}
 92
if(!s.empty()){
 93
puts("-1");
 94
return;
 95 
}
 96
for(int i = 1;i <= lb;i++){
 97
printf("%dn",ans[i]);
 98 
}
 99 }
100
101 int main(){
102
while(scanf("%s",t+1) != EOF){
103 
solve();
104 
}
105
return 0;
106 }

View Code

1.22

cf 620c C - Pearls in a Row

contain 是包含的意思，至少包含有2个不同的数

第一次wa 是因为没有考虑到最长--

然后后几次 wa 是因为 contain

sad-------------------------------------

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<set>
 7 using namespace std;
 8
 9 typedef pair<int,int> pii;
10 typedef long long LL;
11 const int maxn = 5e5+5;
12 int n,m;
13 int a[maxn];
14
15 void solve(){
16
vector<pii> ans;
17
int l = 1,r = 1;
18
for(l = 1;l <= n;){
19
r = l;
20
set<int> s;
21
while(r <= n && s.count(a[r]) == 0){
22 
s.insert(a[r]);
23
r++;
24 
}
25
if(r == n+1) break;
26 
ans.push_back(make_pair(l,r));
27
l = r+1;
28 
}
29
if(ans.size() == 0){
30
puts("-1");
31
return;
32 
}
33
34
int sz = ans.size()-1;
35
ans[sz].second = n;
36
37
printf("%dn",ans.size());
38
for(int i = 0;i < ans.size();i++){
39
printf("%d %dn",ans[i].first,ans[i].second);
40 
}
41 }
42
43 int main(){
44
while(scanf("%d",&n) != EOF){
45
for(int i = 1;i <= n;i++){
46
scanf("%d",&a[i]);
47 
}
48 
solve();
49 
}
50
return 0;
51 }

View Code

cf 620d D - Professor GukiZ and Two Arrays

k = 0,abs (sa - sb)

k = 1, n*m 枚举

k = 2 的时候，用 map<LL,pair<int,int> > 把每一对的 a[i] ,a[j] 存起来

枚举b[i] ,b[j],去找最接近 sa-sb + 2*(b[i]+b[j]) 的 2*（a[i]+a[j]）来更新答案

----今早发现 wa 了--

应该是找到 it,和 it-- 叭


1 #include<cstdio>

2 #include<cstring>

3 #include<cmath>

4 #include<iostream>

5 #include<algorithm>

6 #include<vector>

7 #include<map>

8 using namespace std;

9
 10 typedef long long LL;
 11 typedef pair<int,int> pii;
 12 const int maxn = 5e3+5;
 13 int n,m;
 14 LL a[maxn],b[maxn];
 15
 16 struct node{
 17
int num;
 18 
LL sum;
 19
int l,r;
 20
int ll,rr;
 21 }p[5];
 22
 23 void solve(){
 24
LL res = 1e13+7;
 25
LL sa = 0,sb = 0;
 26
for(int i = 1;i <= n;i++){
 27
sa += a[i];
 28 
}
 29
for(int i = 1;i <= m;i++){
 30
sb += b[i];
 31 
}
 32
p[1].num = 0;
 33
p[1].sum = abs(sa-sb);
 34
p[2].num = 1;
 35
p[3].num = 2;
 36
for(int i = 1;i <= n;i++){
 37
for(int j = 1;j <= m;j++){
 38
LL tmp = abs(sa-sb+2*b[j]-2*a[i]);
 39
// printf("i = %d
j = %d
tmp = %I64dn",i,j,tmp);
 40
if(tmp < res){
 41
res = tmp;
 42
p[2].sum = res;
 43
p[2].l = i;p[2].r = j;
 44 
}
 45 
}
 46 
}
 47
int num = 2;
 48
if(n >= 2 && m >= 2){
 49
map<LL,pair<int,int> > h;
 50
for(int i = 1;i <= n;i++){
 51
for(int j = i+1;j <= n;j++){
 52
h[2*(a[i]+a[j])] = make_pair(i,j);
 53 
}
 54 
}
 55
res = 1e13+7;
 56
map<LL,pair<int,int> >::iterator it;
 57
 58
for(int i = 1;i <= m;i++){
 59
for(int j = i+1;j <= m;j++){
 60
LL tmp = sa-sb+2*(b[i]+b[j]);
 61
it = h.lower_bound(tmp);
 62
for(int k = 0;k < 2;k++){
 63
if(it == h.end()){
 64
it--;
 65
continue;
 66 
}
 67
if(abs(tmp-it->first) < res){
 68
res = abs(tmp-it->first);
 69
p[3].sum = res;
 70
p[3].l = it->second.first;p[3].r = i;
 71
p[3].ll = it->second.second;p[3].rr = j;
 72 
}
 73
if(it == h.begin()) break;
 74
it--;
 75 
}
 76 
}
 77
num = 3;
 78 
}
 79 
}
 80
 81
res = 1e13+7;
 82
for(int i = 1;i <= num;i++){
 83
res = min(res,p[i].sum);
 84 
}
 85
// printf("--res = %I64dn",res);
 86
for(int i = 1;i <= num;i++){
 87
if(p[i].sum == res){
 88
printf("%I64dn",p[i].sum);
 89
if(i == 1){
 90
puts("0");
 91
return;
 92 
}
 93
if(i == 2){
 94
puts("1");
 95
printf("%d %dn",p[i].l,p[i].r);
 96
return;
 97 
}
 98
puts("2");
 99
printf("%d %dn",p[i].l,p[i].r);
100
printf("%d %dn",p[i].ll,p[i].rr);
101 
}
102 
}
103
104 }
105
106 int main(){
107
while(scanf("%d",&n) != EOF){
108
for(int i = 1;i <= n;i++){
109
scanf("%I64d",&a[i]);
110 
}
111
scanf("%d",&m);
112
for(int i = 1;i <= m;i++){
113
scanf("%I64d",&b[i]);
114 
}
115 
solve();
116 
}
117
return 0;
118 }

View Code

1.23

补题

hdu 5612 Baby Ming and Matrix games

知道搜一下就好了，可是一直wa，果然不会搜索--撒都不会----

先是用的double

看bc群里说的会卡double

然后，，搜索真的不会--

搜之前

vis[xx][yy] = 1;

dfs(xx,yy);

搜完再把它改回来阿-唉

然后，就分别用分子，分母来加减乘除

最后，还wa了，是因为 ok 没有初始化

---sad----

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<set>
 6 using namespace std;
 7
 8 typedef long long LL;
 9 char g[105][105];
10 int vis[105][105];
11 int n,m;
12 LL sum;
13 int ok;
14 int dx[4]={1,-1,0,0};
15 int dy[4]={0,0,1,-1};
16
17 LL gcd(LL a,LL b){
18
return (!b)? a:gcd(b,a%b);
19 }
20
21 void dfs(int x,int y,LL fz,LL fm){
22
if(fz == sum && fm == 1){
23
ok = 1;
24
return;
25 
}
26
for(int i = 0;i < 4;i++){
27
int xx = x+2*dx[i];
28
int yy = y+2*dy[i];
29
int nx = x+dx[i];
30
int ny = y+dy[i];
31
if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]) continue;
32
LL nfz = fz,nfm = fm;
33
if(g[nx][ny] == '+'){
34
nfz = nfz+(g[xx][yy]-'0')*fm;
35 
}
36
if(g[nx][ny] == '-'){
37
nfz = nfz-(g[xx][yy]-'0')*fm;
38 
}
39
if(g[nx][ny] == '*'){
40
nfz = nfz*(g[xx][yy]-'0');
41 
}
42
if(g[nx][ny] == '/'){
43
if(g[xx][yy] == '0') continue;
44
nfm = nfm*(g[xx][yy]-'0');
45 
}
46
vis[xx][yy] = 1;
47
LL gc = gcd(nfz,nfm);
48
nfz = nfz/gc;nfm = nfm/gc;
49 
dfs(xx,yy,nfz,nfm);
50
vis[xx][yy] = 0;
51 
}
52 }
53
54 void solve(){
55 
LL fz,fm;
56
ok = 0;
57
for(int i = 1;i <= n;i++){
58
for(int j = 1;j <= m;j++){
59
if(i%2 && j%2){
60
memset(vis,0,sizeof(vis));
61
vis[i][j] = 1;
62
fz = g[i][j]-'0';
63
fm = 1;
64 
dfs(i,j,fz,fm);
65
if(ok == 1){
66
puts("Possible");
67
return;
68 
}
69
vis[i][j] = 0;
70 
}
71 
}
72 
}
73
puts("Impossible");
74 }
75
76 int main(){
77
int T;
78
scanf("%d",&T);
79
while(T--){
80
scanf("%d %d %I64d",&n,&m,&sum);
81
for(int i = 1;i <= n;i++){
82
scanf("%s",g[i]+1);
83 
}
84 
solve();
85 
}
86
return 0;
87 }

View Code

1.24

补题

cf 617c Watering Flowers

就过了6个样例还给过pretest，诶

犯了两个错，去扫最大值得时候，把rr 初始化为 -1，因为更新答案的时候是用 rr+RR，在有些时候，就会让答案少1

然后，只枚举了一个 R,算另一个r

应该两个圆的半径都分别去枚举的时候，取最优的

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 typedef long long LL;
 9 const int maxn = 1e5+5;
10 int a[maxn];
11 int n,m;
12
13 struct node{
14 
LL r,R;
15 
LL x,y;
16 }p[maxn];
17
18 LL x1,x2,y1,y2;
19
20 void solve(){
21
LL ans = 1e18+7;
22
for(int i = 1;i <= n;i++){
23
ans = max(ans,p[i].r);
24
ans = max(ans,p[i].R);
25 
}
26
27
/* for(int i = 1;i <= n;i++){
28 
printf("p[%d].r = %I64d
R = %I64dn",i,p[i].r,p[i].R);
29 
}*/
30
31
for(int i = 1;i <= n;i++){
32
LL RR = p[i].R;
33
LL rr = 0;
34
//
printf("--i == %d RR = %I64dn",i,RR);
35
for(int j = 1;j <= n;j++){
36
if(p[j].R <= RR) continue;
37
if(i == j) continue;
38
rr = max(rr,p[j].r);
39
// printf("i = %d
j = %d
rr = %I64d
RR = %I64dn",i,j,rr,RR);
40 
}
41
ans = min(ans,rr+RR);
42 
}
43
44
for(int i = 1;i <= n;i++){
45
LL rr = p[i].r;
46
LL RR = 0;
47
//
printf("--i == %d RR = %I64dn",i,RR);
48
for(int j = 1;j <= n;j++){
49
if(p[j].r <= rr) continue;
50
if(i == j) continue;
51
RR = max(RR,p[j].R);
52
// printf("i = %d
j = %d
rr = %I64d
RR = %I64dn",i,j,rr,RR);
53 
}
54
ans = min(ans,rr+RR);
55 
}
56
57
printf("%I64dn",ans);
58 }
59
60 int main(){
61
while(scanf("%d %I64d %I64d %I64d %I64d",&n,&x1,&y1,&x2,&y2) != EOF){
62
for(int i = 1;i <= n;i++){
63
scanf("%I64d %I64d",&p[i].x,&p[i].y);
64
p[i].r = (p[i].x-x1)*(p[i].x-x1)+(p[i].y-y1)*(p[i].y-y1);
65
p[i].R = (p[i].x-x2)*(p[i].x-x2)+(p[i].y-y2)*(p[i].y-y2);
66 
}
67 
solve();
68 
}
69
return 0;
70 }

View Code

cf 617d D - Polyline

被hack 之后，输出 2 的情况还是没有想完

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 typedef long long LL;
 9 const int maxn = 1e5+5;
10 int a[maxn];
11 int n,m;
12 int x1,x2,x3,y1,y2,y3;
13
14 void solve(){
15
if((x1 == x2 &&x2 == x3)||(y1 == y2 && y2 == y3)){
16
puts("1");
17
return;
18 
}
19
20
if((y1 == y2)&&(x3>=max(x1,x2) ||x3 <= min(x1,x2))){
21
puts("2");
22
return;
23 
}
24
25
if((y2 == y3)&&(x1>=max(x2,x3) ||x1 <= min(x2,x3))){
26
puts("2");
27
return;
28 
}
29
30
if((y1 == y3)&&(x2>=max(x1,x3) ||x2 <= min(x1,x3))){
31
puts("2");
32
return;
33 
}
34
35
if((x3 == x2)&&(y1>=max(y2,y3) ||y1 <= min(y2,y3))){
36
puts("2");
37
return;
38 
}
39
40
if((x1 == x3)&&(y2>=max(y1,y3) ||y2 <= min(y1,y3))){
41
puts("2");
42
return;
43 
}
44
45
if((x1 == x2)&&(y3>=max(y1,y2) ||y3 <= min(y1,y2))){
46
puts("2");
47
return;
48 
}
49
puts("3");
50 }
51
52 int main(){
53
while(scanf("%d %d",&x1,&y1) != EOF){
54
scanf("%d %d",&x2,&y2);
55
scanf("%d %d",&x3,&y3);
56 
solve();
57 
}
58
return 0;
59 }

View Code

hdu 5145 NPY and girls

给出 n 个数，m 个询问 [l,r] 里面全排列的个数

照着这篇敲的

http://blog.csdn.net/bossup/article/details/39236275

其实还是不会用阿

然后 re 是因为最后再乘以分母的逆元，会超过打表求出来的Inv数组，需要重新算一下


1 #include<cstdio>

2 #include<cmath>

3 #include<cstring>

4 #include<iostream>

5 #include<algorithm>

6 #include<vector>

7 using namespace std;

8

9 typedef long long LL;
 10 const int maxn = 1e5+5;
 11 const int mod = 1e9+7;
 12 int n,m;
 13 LL num[maxn];
 14 int col[maxn],pos[maxn];
 15 LL afac[maxn+10],fac[maxn+10];
 16 LL ans;
 17 LL res[maxn];
 18
 19 struct node{
 20
int l,r;
 21
int id;
 22 }q[maxn];
 23
 24 bool cmp(node a,node b){
 25
if(pos[a.l] == pos[b.l])
 26
return a.r<b.r;
 27
return pos[a.l] < pos[b.l];
 28 }
 29
 30 LL Q_pow(LL x,LL y){
 31
LL res = 1;
 32
x %= mod;
 33
while(y){
 34
if(y&1) res = res*x%mod;
 35
x = x*x%mod;
 36
y >>= 1;
 37 
}
 38
return res;
 39 }
 40
 41 void Pre(){
 42
fac[0]=1;
 43
for(int i = 1;i <= maxn;i++){
 44
fac[i] = fac[i-1]*(LL)i%mod;
 45 
}
 46
afac[maxn]=Q_pow(fac[maxn],mod-2);
 47
for(int i = maxn;i>=1;i--){
 48
afac[i-1] = afac[i]*i%mod;
 49 
}
 50 }
 51
 52 void update(int x,int d){
 53
ans = ans*afac[num[col[x]]]%mod;
 54
num[col[x]] += d;
 55
ans = ans*fac[num[col[x]]]%mod;
 56 }
 57
 58 long long Inv(long long x)///mod为质数
 59 {
 60
long long r, y;
 61
for(r = 1, y = mod - 2; y; x = x * x % mod, y >>= 1)
 62
(y & 1) && (r = r * x % mod);
 63
return r;
 64 }
 65
 66 int main(){
 67 
Pre();
 68
int bk,pl,pr,id;
 69
int T;
 70
scanf("%d",&T);
 71
while(T--){
 72
scanf("%d %d",&n,&m);
 73
memset(num,0,sizeof(num));
 74
bk = ceil(sqrt(1.0*n));
 75
for(int i = 1;i <= n;i++){
 76
scanf("%d",&col[i]);
 77
pos[i]=(i-1)/bk;
 78 
}
 79
for(int i = 0;i < m;i++){
 80
scanf("%d %d",&q[i].l,&q[i].r);
 81
q[i].id = i;
 82 
}
 83
sort(q,q+m,cmp);
 84
pl = 1,pr = 0;
 85
ans = 1;
 86
memset(res,0,sizeof(res));
 87
for(int i = 0;i < m;i++){
 88
id = q[i].id;
 89
if(q[i].l == q[i].r){
 90
res[id] = 1;
 91
continue;
 92 
}
 93
if(pr < q[i].r){
 94
for(int j = pr+1;j <= q[i].r;j++){
 95
update(j,1);
 96 
}
 97 
}
 98
else{
 99
for(int j = pr;j >q[i].r;j--){
100
update(j,-1);
101 
}
102 
}
103
pr = q[i].r;
104
if(pl<q[i].l){
105
for(int j = pl;j<q[i].l;j++){
106
update(j,-1);
107 
}
108 
}
109
else{
110
for(int j=pl-1;j>=q[i].l;j--){
111
update(j,1);
112 
}
113 
}
114
pl = q[i].l;
115
LL fz = (q[i].r-q[i].l+1);
116
LL tmp = fac[fz]*Inv(ans)%mod;
117
res[id] = tmp;
118 
}
119
for(int i = 0;i < m;i++){
120
printf("%I64dn",res[i]);
121 
}
122 
}
123
return 0;
124 }

View Code

hdu 5613Baby Ming and Binary image

看题解补的，暴力枚举最左边一列，2^n-2，然后算这 2^n-2个矩阵里面有多少个满足的

wa了好几次，是因为递推完一个矩阵的时候，要验算一下最后一行是不是都是0


1 #include<cstdio>

2 #include<cstring>

3 #include<iostream>

4 #include<algorithm>

5 #include<vector>

6

7 int n,m;

8 int g[55][105];

9 int res[55][105];
 10 int a[55][105];
 11 int dx[8]={0,-1,-1,-1,0,1,1,0};
 12 int dy[8]={1,1,0,-1,-1,-1,0,0};
 13
 14 int ok(){
 15
/* for(int i = 1;i <= n;i++){
 16 
for(int j = 1;j <= m;j++){
 17 
printf("%d ",a[i][j]);
 18 
}
 19 
printf("n");
 20 
}
 21 
printf("----newnewnewnwewn");*/
 22
 23
for(int i = 1;i <= n;i++){
 24
for(int j = 1;j <= m;j++){
 25
int tmp = 0;
 26
for(int k = 0;k < 8;k++){
 27
int nx = i+dx[k];
 28
int ny = j+dy[k];
 29
if(nx<1||nx>n||ny<1||ny>m) continue;
 30
tmp += a[nx][ny];
 31 
}
 32
//
printf("i = %d
j = %d
tmp=%dn",i,j,tmp);
 33
if(g[i][j] == tmp) a[i+1][j+1]=0;
 34
else if(g[i][j]== tmp+1){
 35
if(i+1 <= n && j+1 <= m) a[i+1][j+1]=1;
 36
else return 0;
 37 
}
 38
else{
 39
return 0;
 40 
}
 41
/* printf("----debug----n");
 42 
for(int i = 1;i <= n;i++){
 43 
for(int j = 1;j <= m;j++){
 44 
printf("%d ",a[i][j]);
 45 
}
 46 
printf("----n");
 47 
}
 48 
printf("----debug----n");*/
 49 
}
 50 
}
 51
for(int j=1;j <= m;j++){
 52
if(a[n][j] != 0) return 0;
 53 
}
 54
return 1;
 55 }
 56
 57 void solve(){
 58
int N = n-2;
 59
int c = 0;
 60
for(int i = 0;i < (1<<N);i++){
 61
memset(a,0,sizeof(a));
 62
for(int j = 0;j < N;j++){
 63
if(i&(1<<j)){
 64
a[j+2][1]=1;
 65 
}
 66 
}
 67
if(ok()) {
 68
c++;
 69
memcpy(res,a,sizeof(a));
 70 
}
 71 
}
 72
// printf("cccc = %dn",c);
 73
if(c == 1){
 74
for(int i = 1;i <= n;i++){
 75
for(int j = 1;j <= m;j++){
 76
if(j!=m) printf("%d ",res[i][j]);
 77
else printf("%dn",res[i][j]);
 78 
}
 79 
}
 80 
}
 81
else if(c == 0){
 82
puts("Impossible");
 83 
}
 84
else{
 85
puts("Multiple");
 86 
}
 87 }
 88
 89 int main(){
 90
int T;
 91
 92
scanf("%d",&T);
 93
while(T--){
 94
scanf("%d %d",&n,&m);
 95
for(int i = 1;i <= n;i++){
 96
for(int j = 1;j <= m;j++){
 97
scanf("%d",&g[i][j]);
 98 
}
 99 
}
100 
solve();
101 
}
102
return 0;
103 }