题目链接
Codeforces Round #578 (Div. 2)
A
思路
500分的题目，直接暴力模拟
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
int n,ans[10];
string s;
int main(void){
cin>>n>>s;
for(int i=0;i<n;i++){
if(s[i]=='L'){
for(int j=0;j<10;j++)if(ans[j]==0){ans[j]=1;break;}
}
else if(s[i]=='R'){
for(int j=9;j>=0;j--)if(ans[j]==0){ans[j]=1;break;}
}
else {
ans[s[i]-'0']=0;
}
}
for(int i=0;i<10;i++)cout<<ans[i];
return 0;
}
|
B
题目详情
给出一个序列n，代表每个柱子的高度,如果|a[i+1]-a[i]|<=k那么就能跳下下一个柱子，求是否能够跳到最后一根柱子。
在每根柱子上时，可以有3种操作：
1.捡起石头
2.放石头叠柱子的高度
3.往下一个柱子上跳
思路
贪心思想，贪心让自己手上的石头数量最多就好了。
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
#define ll long long
ll a[maxn];
ll n,m,k;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
cin>>n>>m>>k;
bool ok = true;
for(int i=0;i<n;i++)
{
scanf("%I64d",&a[i]);
}
for(int i=0;i<n-1;i++)
{
if(a[i]>=a[i+1])
{
m+=(a[i]-a[i+1]+k)>=a[i]?a[i]:(a[i]-a[i+1]+k);
}
else
{
if(a[i+1]-a[i]>=k)
{
m-=(a[i+1]-k-a[i]);
}
else
{
m+=(a[i]-a[i+1]+k)>a[i]?a[i]:(a[i]-a[i+1]+k);
}
}
if(m<0)
{
ok=false;
break;
}
}
if(ok)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
|
C
题目链接
C
题目描述
给出两个圆，一个内圆一个外圆,内圆被平均分成n份，外圆被分成m份。12点钟方向有一堵墙，
内圆的坐标为顺时针数(1,i)其中1<=i<=n，外圆也如此。
现在有q个询问，求出x，y能否到达i，j这个扇区。
思路
内圆被平均分成n份，也就是(1,1/n),(1,2/n)···(1,n/n).
外圆被平均分成m份，也就是(1,1/m),(1,2/m)···(1,m/m).
那么他们之间共同分成的区域也就是
令g=gcd(n,m);整个被分为(1,1/g),(1,2/g)···(1,g/g).
对于每一个询问，判断所在的部分g’就好了。
代码实现
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;
#define ll long long
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
ll n,m,q;
ll sx,sy,ex,ey;
int main()
{
cin>>n>>m>>q;
ll g = gcd(n,m);
while(q--)
{
cin>>sx>>sy>>ex>>ey;
sy--;
ey--;
long long seps = (sx==1?sy/(n/g):sy/(m/g));
long long sepe = (ex==1?ey/(n/g):ey/(m/g));
cout<<(seps==sepe?"YES\n":"NO\n");
}
}
|
D
题目链接
D
题目描述
给出一个NN的矩阵，你有一次机会把KK的矩阵变成全W，求使用这次机会后，矩阵的某一行或者某一列全为1则答案+1.
思路
这题的思路很巧妙，利用了二维前缀和的思想。我们可以先预处理，对于每一行i，先找出该行的最左边的位置l，以及最右边的位置r，那么我们想要使得这一行的全部都变成W的话我们所有选取的范围就是row>=max(0,i-k+1).i>row.对于col(列)而言。
col>=max(r-k+1,0);l>col.所以就能计算出使得当前行能够变成全W的范围。
这里运用了二维前缀和的思想，在sr，sc上++，那么当脱离这个范围的时候就需要-1，于是[sr][ec+1],[er+1][sc]都要-1.
然后[er+1][ec+1]需要+1，这样我们在处理前缀和的时候就可以形成一个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
75
76
77
78
79
80
81
82
83
84
| #include<bits/stdc++.h>
using namespace std;
char dat[2050][2050];
int mp[2050][2050];
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int base = 0;
for(int i=0;i<n;i++)
{
scanf("%s",dat[i]);
}
for(int row=0;row<n;row++)
{
int bmin=-1,bmax=-1;
for(int i=0;i<n;i++)
{
if(dat[row][i]=='B')
{
if(bmin==-1)
{
bmin=i;
}
bmax = i;
}
}
if(bmin==-1)
{
base++;
continue;
}
int sr = max(0,row-k+1);
int er = min(n-1,row);
int sc = max(0,bmax-k+1);
int ec = min(n-1,bmin);
if(sr<=er&&sc<=ec)
{
mp[sr][sc]++;
mp[sr][ec+1]--;
mp[er+1][sc]--;
mp[er+1][ec+1]++;
}
}
for(int col=0;col<n;col++)
{
int bmin=-1,bmax=-1;
for(int i=0;i<n;i++)
{
if(dat[i][col]=='B')
{
if(bmin==-1)bmin=i;
bmax = i;
}
}
if(bmin==-1)
{
base++;
continue;
}
int sr = max(0,bmax-k+1);
int er = min(n-1,bmin);
int sc = max(0,col-k+1);
int ec = min(n-1,col);
if(sr<=er&&sc<=ec)
{
mp[sr][sc]++;
mp[sr][ec+1]--;
mp[er+1][sc]--;
mp[er+1][ec+1]++;
}
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
mp[i+1][j]+=mp[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
mp[i][j+1]+=mp[i][j];
int ans = 0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ans=max(ans,base+mp[i][j]);
cout<<ans<<endl;
}
|
E
题目链接
E
题目描述
连接最长的相同后缀前缀
思路
直接暴力，（PS:不明白这道题的意义何在
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
string s,ans;
int main()
{
ans = "";
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s;
if(i==0){
ans+=s;
continue;
}
bool ok = false;
int len = ans.size(),len1=s.size();
for(int j=len1-1;j>=0;j--)
{
if(ans[len-1]==s[j]&&len>=j+1)
{
int templ = len - 1;
int tempj = j;
while(tempj>=0)
{
if(ans[templ]!=s[tempj])break;
templ--,tempj--;
}
if(tempj==-1)
{
ok = true;
ans+=s.substr(j+1,len1-j);
break;
}
}
}
if(!ok)ans+=s;
}cout<<ans<<endl;
}
|