比赛地址：Dashboard - Codeforces Round 955 (Div. 2, with prizes from NEAR!) - Codeforces
一个月没做了，期末周太忙了呜呜呜
D太遗憾了，结束7分钟后就出代码了，后来一测一发过，，前中段太唐了
A
题意：给出两个比分，一段时间后又给出一个比分，问这期间两队有没有可能出现平局的局面。
比较一下大小就行，水题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if(a<b)
{
if(c<d)cout<<"YES\n";
else cout<<"NO\n";
}
else
{
if(c>d)cout<<"YES\n";
else cout<<"NO\n";
}
}
}
|
B
题意：给出 $x,y,k$ ，一共操作 $k$ 次，每次操作先对 $x$ 加1，若 $x$ 是 $y$ 的倍数，那么对 $x$ 除以 $y$ 知道不能整除。求最后的 $x$ 。$x,y,k\leq 10^9$
一直对 $x$ 进行除操作，每次除的时候记录一下补了多少才能整除。最后当 $x$ 变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
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int x,y,k;
cin>>x>>y>>k;
int e=y-x%y;
if(k<e)
{
cout<<x+k<<endl;
continue;
}
x=x/y+1;
k-=e;
int acc=0;
bool flag=0;
while(x!=1)
{
if(k<y-x%y && x%y!=0 )
{
cout<<x+k<<endl;
flag=1;
break;
}
if(x%y!=0 )k-=y-x%y;
x=(x-1)/y+1;
}
int ex=y-1;
k=k%ex;
if(!flag)
{
cout<<x+k<<endl;
}
}
}
|
C
有 $n$ 个数，每回合可以从左边依次拿走若干个数，若满足本回合拿走的数的和在区间 $[l,r]$ ，那么赢得一次。求最大获胜次数。
最开始用的贪心，属实小脑萎缩了太唐了
考虑 $dp$ ，设计状态 $dp[i]$ 表示最后一个取第 $i$ 个数时最大获胜次数。对每一个 $i$ ，找以 $i$ 结尾的一个最短区间 $[pos,i]$ 使得和在区间 $[l,r]$ 中，若存在，那么 $dp[i]=dp[pos-1]+1$ ，否则 $dp[i]=dp[i-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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200005];
int dp[200005];
int pre[200005];
int n,l,r;
int find(int pos)
{
if(pre[pos]<l)return 0;
int ll=1,rr=pos;
while(ll<rr)
{
int mid=(ll+rr+1)>>1;
if(pre[pos]-pre[mid-1]>=l)ll=mid;
else rr=mid-1;
}
return ll;
}
void solve()
{
cin>>n>>l>>r;
for(int i=1;i<=n+2;i++)dp[i]=0,pre[i]=0;
for(int i=1;i<=n;i++)cin>>a[i],pre[i]=pre[i-1]+a[i];
int ans=0;
int t=0;
for(int i=1;i<=n;i++)
{
int x=find(i);
if(x==0)dp[i]=0;
else if(pre[i]-pre[x-1]>r)dp[i]=dp[i-1];
else dp[i]=dp[x-1]+1;
}
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
cout<<ans<<endl;
}
signed main()
{
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
D
题意：给一个 $n\times m$ 的网格，每个格子有一个高度，同时所有格子被分为两类。每次可以对一个 $k\times k$ 的网格进行每个元素加 $c$ 的操作，$c$ 为自己决定。能否使有限次操作后，两类格子的和相等。
设 $tot=sum_1-sum_2$ ，那么在每个 $k\times k$ 的网格中，每次操作使答案变化 $c\times d_{0,1}$ ，即 $c$ 乘上网格中两类网格的数量差。因此可以得到最后的答案只与 $d$ 有关，那么可以处理出所有的 $d$ ，最后只需满足：
$$
c_1d_1+c_2d_2+…+c_{cnt}d_{cnt}=sum
$$
即判断 $sum$ 能否整除 $gcd(d_1,d_2,…d_{cnt})$。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
int mp[600][600];
int tp[600][600];
int w[260000];
int n,m,k;
int pre[600][600];
void solve()
{
cin>>n>>m>>k;
int tot=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
}
}
char c[600][600];
for(int i=1;i<=n;i++)cin>>c[i]+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(c[i][j]=='1')tp[i][j]=1,tot+=mp[i][j];
else tp[i][j]=-1,tot-=mp[i][j];
}
}
if(tot==0)
{
cout<<"YES\n";
return ;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
pre[i][j]=tp[i][j]+pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1];
}
}
int cnt=0;
for(int i=k;i<=n;i++)
{
for(int j=k;j<=m;j++)
{
w[++cnt]=pre[i][j]-pre[i-k][j]-pre[i][j-k]+pre[i-k][j-k];
}
}
int gcd=w[1];
for(int i=1;i<=cnt;i++)gcd=__gcd(gcd,w[i]);
if(gcd==0)
{
cout<<"NO\n";
return ;
}
if(tot%gcd==0)cout<<"YES\n";
else cout<<"NO\n";
}
signed main()
{
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
微信
支付宝
