[原创]Codeforces Round #420 (Div. 2)

2017-06-27 19:07:39 Tabris_ 阅读数:203


博客爬取于2020-06-14 22:39:55
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/73822126


A Okabe and Future Gadget Laboratory

——————————————————————————————————————————

简单SB题,
问你矩阵中所有大于11的数能否用所在行的一个数加上所在列的一个数表示 ,如果都能就YES,否则NO

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
int n;
int a[55][55];

bool solve(int x,int y){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[x][y]==a[x][i]+a[j][y]) return true;
}
}
return false;
}

int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
int flag=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==1)continue;
if(solve(i,j))continue;
flag=false;break;
}
if(!flag) break;
}

if(flag) puts("Yes");
else puts("No");

return 0;
}

B Okabe and Banana Trees

——————————————————————————————————————————

还是SB题,暴力找O(m×b)O(m\times b)都不会超时

但是显然答案一定在线下方第一个点,

而直到每个点后的答案是能O(1)计算的

所以O(b)O(b)维护(1+x)x/2(y+1)+(1+y)(y)/2(x+1)(1+x)*x/2*(y+1)+(1+y)*(y)/2*(x+1)的最小值即可

1
2
3
4
5
6
7
8
9
10
int main(){
LL m,b,ans=0;
scanf("%lld%lld",&m,&b);
for(LL y=0,x;y<=b;y++){
x=(b-y)*m;
ans = max(ans,(1+x)*x/2*(y+1)+(1+y)*(y)/2*(x+1));
}
printf("%lld\n",ans);
return 0;
}

C Okabe and Boxes

——————————————————————————————————————————

让你维护一个栈,你可以将栈里面的元素重新排列,现在问你至少重新排列多少回 能让出栈的顺序为升序


就是在维护这个栈的操作,
进栈的时候一样

出站的时候看栈顶是不是预期的那个数,是的话就重新排列下即可

而这里的重新排列 可以用清空栈来代替

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
char s[22];
int mystack[N],len;
int a[N],la,cnt,ans;

const int INF = 3e6;

int main(){
int n;len=la=cnt=ans=0;
scanf("%d",&n);
for(int i=1,x;i<=n*2;i++){
scanf("%s",s);
if(s[0]=='a'){
scanf("%d",&x);
mystack[++len]=x;
}
else {
cnt++;
if(len&&mystack[len]==cnt) len--;
else if(len) ans++,len=0;
}
}
printf("%d\n",ans);
return 0;
}

D Okabe and City

——————————————————————————————————————————

N*M的二维矩阵,有K个位置时初始就是亮着的,一个人要走在当时亮着的格子从(1,1)到(n,m)
站在最初是亮着位置可以花费1来让某一行或某一列全变量,
问你最小花费


同时只能点亮某一行或某一列,那么一定是在最初两者的位置临近的两个行/两个列和本身所在的行/列,

再加上格子相邻的地方

按照这两种规则进行建图计算最短路就行了,

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
struct node {
int to,next,w;
}G[N];

int head[N],cnt,tot;

void add(int u,int v,int w){
G[cnt].w=w,G[cnt].to=v,G[cnt].next=head[u],head[u]=cnt++;
}

int d[N],vis[N];
void SPFA(int s,int t,int n){
const int INF = (~(1<<31))>>1;
for(int i=0;i<=n;i++) d[i]=INF,vis[i]=0;
queue<int >q;
q.push(s);d[s]=0,vis[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u],to,w;i!=-1;i=G[i].next){
to=G[i].to;
w =G[i].w;
if(d[to]>d[u]+w){
d[to]=d[u]+w;
if(vis[to])continue;
vis[to]=1;q.push(to);
}
}
}
if(d[t]==INF) puts("-1");
else printf("%d\n",d[t]);
}

int n,m,k;
int x[11111],y[11111];
int a[11111],b[11111];

int main(){
memset(head,-1,sizeof (head));

scanf("%d%d%d",&n,&m,&k);

cnt=0,tot=k;

for(int i=1;i<=n;i++) x[i]=++tot;
for(int j=1;j<=m;j++) y[j]=++tot;

int flag=0,s=0,t=0;
for(int i=1;i<=k;i++){
scanf("%d%d",&a[i],&b[i]);
}
for(int i=1;i<=k;i++){
add(i,x[a[i]],1),add(x[a[i]],i,0);
if(x[a[i]-1]) add(i,x[a[i]-1],1),add(x[a[i]-1],i,0);
if(x[a[i]+1]) add(i,x[a[i]+1],1),add(x[a[i]+1],i,0);
add(i,y[b[i]],1),add(y[b[i]],i,0);
if(y[b[i]-1]) add(i,y[b[i]-1],1),add(y[b[i]-1],i,0);
if(y[b[i]+1]) add(i,y[b[i]+1],1),add(y[b[i]+1],i,0);

for(int j=1;j<i;j++) if(abs(a[i]-a[j])+abs(b[i]-b[j])<=1) add(i,j,0),add(j,i,0);

if(a[i]==1&&b[i]==1) s=i;
if(a[i]==n&&b[i]==m) t=i;
}

if(!t) t=++tot;
add(x[n],t,0);
add(y[m],t,0);

SPFA(s,t,tot);
return 0;
}

1

E Okabe and El Psy Kongroo

——————————————————————————————————————————

有n条线段,线段平行于x坐标, 每次只能走在线段下方,从(x,y)能走到(x+1,y+1)(x+1,y)(x+1,y-1)这三个位置,问你最后到(k,0)的方案数,


简单的矩阵快速幂

只与必须在线段下方的限制,我们可以再计算之前将不合格的点清0即可

注意I64 要不然会GG

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
89
90
91
92
93
94
95
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 3e6+7;
const int MOD = 1e9+7;
# define abs(x) ((x)>0?(x):-(x))

inline LL read(){
LL x=0;char ch=getchar();
for(;ch<'0'||'9'<ch;ch=getchar());
for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
return x;
}

/***************************************************************/

const int M = 20;
struct Matrix{
LL m[M][M];
void clearO(){
for(int i=0; i<M; i++)
for(int j=0; j<M; j++)
m[i][j]= 0;
}
void clearE(){
for(int i=0; i<M; i++)
for(int j=0; j<M; j++)
m[i][j]= (i==j);
}
void display(){
for(int i=0; i<M; i++){
for(int j=0; j<M; j++)
printf("%d ",m[i][j]);
puts("");
}
}
};
Matrix operator * (Matrix &a,Matrix &b){
Matrix c;c.clearO();
for(int k=0; k<M; k++)
for(int i=0; i<M; i++){
if(a.m[i][k] <= 0) continue;
for(int j=0; j<M; j++){
if(b.m[k][j] <= 0) continue;
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
}
}
return c;
}
Matrix operator ^ (Matrix &a,LL b){
Matrix c;c.clearE();
while(b){
if(b&1) c= c * a ;
b >>= 1;
a = a * a ;
}
return c;
}

int n;
LL k;
LL a[111],b[111];
int c[111];

int main(){
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld%lld%d",&a[i],&b[i],&c[i]);
b[n]=k;

Matrix aa,bb;
aa.clearO();aa.m[0][0]=1;
for(int i=1;i<=n;i++){

bb.clearO();
for(int j=0;j<=15;j++){
if(j-1>=0) bb.m[j][j-1]=1;
bb.m[j][j ]=1;
if(j+1<=15) bb.m[j][j+1]=1;
}
// bb.display();
for(int j=0;j<=15;j++){
for(int k=0;k<=15;k++){
if(j<=c[i]&&k<=c[i]) continue;
aa.m[j][k]=bb.m[j][k]=0;
}
}
bb=bb^(b[i]-a[i]);
aa=aa*bb;
}

printf("%lld\n",aa.m[0][0]);

return 0;
}