codeforces 209 div.2

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A:如果边缘有点,那么次数就是2,如果边缘没点,只有中间有点,那么次数是4,和点的个数无关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define mp make_pair


int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
int val;
bool have = false;
for(int i = 1; i <= n; i++)
for(int j = 1 ; j <= m; j++){
scanf("%d",&val);
if(val){
if(i == 1 || i == n || j == 1 || j == m)
have = true;
}
}
if(have) puts("2");
else puts("4");
}
return 0;
}

B:把题目给出来的式子,称为左式和右式,左式 - 右式 = 2k

例如n=4,考虑排列1 2 3 4 5 6 7 8,将其分为上下两部分

1 3 5 7

2 4 6 8

左式 = |1-2| + |3-4| + |5-6| + |7-8| = 4

右式 = |1 + 3 + 5 + 7 - 2 - 4 -6 -8| = 4

左式 - 右式 = 0

这个排列是比较特殊的,结果为0

看看上面的式子,对应的项,如果上下交换一组,左式的结果是不会改变的,但是右式的结果会改变

2 3 5 7

1 4 6 8

左式 = 4

右式 = 2

左式 - 右式 = 2

所以每交换一组,结果就增加2

因为左式 - 右式 = 2k,所以就是交换k组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define mp make_pair
#define N 50010

int a[N],b[N],n,m;

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i = 0,val = 1; i < n; i++,val+=2)
a[i] = val;
for(int i = 0,val = 2; i < n; i++,val+=2)
b[i] = val;
for(int i = 0 ; i < m; i++)
swap(a[i],b[i]);
for(int i = 0 ; i < n; i++)
printf("%d %d ",a[i],b[i]);
puts("");
}
return 0;
}

—————————- PYTHON ——————————-

  1. 输入数据:raw_input(),split()函数进行分片
  2. 利用map函数,将分片后的每个字符串转化为数字 map(int, ….) , map还有很多用法非常强大
    n , m = map(int , raw_input().split())
    等价于
    scanf(“%d%d”,&n,&m);
  3. 程序中需要用到数组,在python中,用列表这种类型实现
    a = []
    b = []
    是创建两个列表,创建列表有很多方法,这种方法创建后得到两个空列表
  4. a.append(),append()方法是在列表的结尾处插入新元素
  5. for循环,for需要用到循环计数器,一般都用range()实现,range的具体内容不详说
    for i in range(n)
  6. swap,python中没有这个函数,但要实现它却相当简单,程序中
    a[i] , b[i] = b[i] , a[i]
    等价于
    swap(a[i],b[i])
  7. 打印,python中 print x 然后会换行,这里我们要打印一系列的元素不能换行,方法就是在最后加上一个,
    print x, 打印完x后不会换行而是空格
1
2
3
4
5
6
7
8
9
10
11
n , m = map(int , raw_input().split())
a = []
b = []
for i in range(n):
a.append(1 + i*2)
for i in range(n):
b.append(2 * (i+1))
for i in range(m):
a[i] , b[i] = b[i] , a[i]
for i in range(n):
print a[i],b[i]

—————————- PYTHON ——————————-

C:这个问题,可以迭代,并且每次搞掉一部分后,得到的是一个等价的问题
观察每个分子的指数,对于分子不为0的指数放到一边,在这些指数中找到最小的那个,minm;对于指数为0的
即x^0 = 1,那么把它累加到一个变量Z中
扫完后,主要是观察Z这个变量,看看Z能分解出多少个X,如果一个X都分解不出来,那么迭代已经结束了
如果Z能分解为nz个x,拿nz和minm比较,now = min(minm,nz),当前能约掉的数字就是x^now
Z = Z / (x^now),然后原来每个指数也要更新 m[i] -= now,如果m[i]也变为0,则再次累加到Z中
其实分子是很多项的和,分母是x的幂次,求GCD,就是在分子中提出一个公共的x的幂次,能不能提出,主要取决于Z
每次提出一个x的幂次并且约掉后,又回到了一个等价的问题,再用同样的方法去迭代
另外注意,如果分母的指数已经变为0,那么迭代也结束了
代码写得不好,搞了90多行,后来才看到,数据给出来的时候保证了a1<=a2<=a3<=a4<=a5……
这样的话可以精简很多代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define MOD 1000000007
#define INF 11111111111111111LL
#define N 100010
#define LL long long
#define pii pair<int,int>
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define mp make_pair

LL n,mark,x,m[N];

LL pow_mod(LL a,LL m){
if(m == 0LL) return 1LL;
if(m == 1LL) return a % MOD;
LL temp = pow_mod(a , m/2) % MOD;
temp = (temp * temp) % MOD;
if(m & 1) temp = (temp * a) % MOD;
return temp;
}

LL get_nz(LL Z){
LL cnt = 0;
while(Z != 0 && Z % x == 0){
cnt++; Z /= x;
}
return cnt;
}

LL updata_now(LL minm,LL nz,LL tot,LL Z){
LL res = min(minm,tot);
if(Z != 0) res = min(res,nz);
return res;
}

void updata_Z(LL &Z , LL now){
if(Z == 0LL) return ;
while(now){
Z /= x; now--;
}
}

int main(){
LL tot,sum,minm,now,Z,nz,ans;
while(scanf("%I64d%I64d",&n,&x)!=EOF){
tot = sum = Z = 0LL;
minm = INF;
ans = 1LL;
for(int i = 0; i < n; i++){
scanf("%I64d",&m[i]);
tot += m[i];
}
for(int i = 0; i < n; i++){
m[i] = tot - m[i];
if(m[i] == 0LL) Z++;
else minm = min(minm,m[i]);
}
nz = get_nz(Z);
now = updata_now(minm,nz,tot,Z);
while(now > 0LL){
if(Z != 0LL && nz == 0LL) break;
sum += now;
tot -= now;
updata_Z(Z,now);
minm = INF;
for(int i = 0 ; i < n; i++){
if(m[i] == 0LL) continue;
m[i] -= now;
if(m[i] == 0LL) Z++;
else minm = min(minm,m[i]);
}
nz = get_nz(Z);
now = updata_now(minm,nz,tot,Z);
}
ans = pow_mod(x,sum);
printf("%I64d\n",ans);
}
return 0;
}

D;想了个很简单的方法,理论复杂度是O(n^2),不过细想,根据这个题目的性质,是很难出得到O(n^2)
的数据,基本上就是O(n)的复杂度,然后编码提交就通过了,事后再思考,的确题目本身的性质决定了这个算法可行
以ai为标准,向两边找,看看然后哪些是ai的倍数,即能被ai整除,找到第一个断开的位置为止,那么就可以知道,
以ai为标准,能找到的序列长度,记为cnt[i]
这个寻找的过程,可以优化一下(赛后看一些人的代码,直接很暴力地找)
先从左边扫一遍,用L[i]记录,ai的左边有多少个连续能被ai整除的数字
如果ai-1 % ai != 0 , L[i] = 0(一个都 没有,因为要连续)
如果ai-1 % ai == 0 , L[i] = L[i-1]+1,还没完,还要从当前继承的位置开始,再向左找(这里理论是O(n^2))
再从右边扫一遍,用R[i]记录,ai的右边有多少个连续能被ai整除的数字
如果ai+1 % ai != 0 , R[i] = 0
如果ai+1 % ai == 0 , R[i] = R[i+1]+1,还要从 当前继承的位置开始,再向右找
最后cnt[i] = L[i] + R[i] + 1; 即以ai为标准,能被ai整除的数的个数(包括它自己)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define N 300010
#define LL long long
#define pii pair<int,int>
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define mp make_pair


int a[N],n;
int L[N],R[N],cnt[N];
int max_num,num,List[N];

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
L[1] = 0;
for(int i = 2; i <= n; i++)
if(a[i-1] % a[i] == 0){
L[i] = L[i-1] + 1;
int index = i - L[i] - 1;
while(index >= 1 && a[index] % a[i] == 0){
L[i]++; index--;
}

}
else L[i] = 0;
R[n] = 0;
for(int i = n-1; i >= 1; i--)
if(a[i+1] % a[i] == 0){
R[i] = R[i+1] + 1;
int index = i + R[i] + 1;
while(index <= n && a[index] % a[i] == 0){
R[i]++; index++;
}
}
else R[i] = 0;
max_num = 0;
for(int i = 1; i <= n; i++){
cnt[i] = L[i] + 1 + R[i];
max_num = max(max_num,cnt[i]);
}
/*
puts("L");
for(int i = 1; i <= n; i++)
printf("%d ",L[i]);
puts("");
puts("R");
for(int i = 1; i <= n; i++)
printf("%d ",R[i]);
puts("");
puts("cnt");
for(int i = 1; i <= n; i++)
printf("%d ",cnt[i]);
puts("");
*/
num = 0;
for(int i = 1; i <= n; i++)
if(cnt[i] == max_num){
int index = i - L[i];
List[num++] = index;
}
sort(List,List+num);
int m = 1;
for(int i = 1; i < num; i++)
if(List[i] != List[i-1])
List[m++] = List[i];
printf("%d %d\n",m,max_num-1);
for(int i = 0; i < m; i++)
printf("%d ",List[i]);
puts("");
}
return 0;
}

E:题意——给一个n*n的矩阵图,并给出起始位置,图中1表示灯亮0表示灯灭,任务是关闭所有的灯,不能超过 300w步。四个方向可以走,可走的条件是,该方向上至少有1个1(即这一行或这一列上至少1个1)。
做法是,如果dfs走到一个格子,当前为0,那么先把它开了,因为这样做才确保了有“回来的路”。从起点一直dfs,dfs回溯的时候才把灯灭掉,然后走的过程一直记录步骤(回来的步骤也要记录)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
using namespace std;
#define N 510
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))


const int dx[4] = {0,-1,0,1};
const int dy[4] = {-1,0,1,0};
const char go[5] = "LURD";
const char back[5] = "RDLU";
int g[N][N],n,stx,sty;
bool vis[N][N];
queue<char>step;

bool check(int x,int y,int dir){
if(x < 1 || x > n || y < 1 || y > n) return false;
if(vis[x][y]) return false;
if(dir == 0){
for( ; y > 0; y--)
if(g[x][y]) return true;
}
else if(dir == 1){
for( ; x > 0; x--)
if(g[x][y]) return true;
}
else if(dir == 2){
for( ; y <= n; y++)
if(g[x][y]) return true;
}
else{
for( ; x <= n; x++)
if(g[x][y]) return true;
}
return false;
}

void dfs(int x,int y,int dir){
vis[x][y] = true;
if(g[x][y] == 0) step.push('1');
g[x][y] = 1;
for(int k = 0; k < 4; k++){
int xx = x + dx[k];
int yy = y + dy[k];
if(!check(xx,yy,k)) continue;
step.push(go[k]);
dfs(xx,yy,k);
}
step.push('2');
g[x][y] = 0;
if(dir != -1) step.push(back[dir]);
}

int main(){
while(scanf("%d%d%d",&n,&stx,&sty)!=EOF){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d",&g[i][j]);
cl(vis,false);
while(!step.empty()) step.pop();
dfs(stx,sty,-1);
bool res = true;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(g[i][j]){
res = false; break;
}
if(!res) puts("NO");
else{
puts("YES");
while(!step.empty()){
printf("%c",step.front()); step.pop();
}
puts("");
}
}
return 0;
}