Codeforces Round 1703&1702

上班阶段的忙里偷闲(甚至还没做完)

因为只是div4和div3 我又拖了很久没有写()所以不怎么写题意 就贴个代码

1703A: YES or YES?

题目链接

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
string s; cin>>s;
for(int i=0; i<s.size(); ++i) s[i]=tolower(s[i]);
return puts(s=="yes"?"YES":"NO");
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1703B: ICPC Balloons

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
int n,ans(0); string s;
cin>>n>>s; vector<int>cnt(26);
for(auto c: s){
if(!cnt[c-'A']) ans+=2;
else ans++;
cnt[c-'A']++;
}
return printf("%d\n",ans);
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1703C: Cypher

题目链接

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
int n; cin>>n;
vector<int>vv(n);
for(int i=0; i<n; ++i)
cin>>vv[i];
for(int i=0; i<n; ++i){
int k; string s;
cin>>k>>s;
for(auto c: s){
if(c=='U') vv[i]--;
else vv[i]++;
}
cout<<(vv[i]+10)%10<<' ';
}
return printf("\n");
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1703D: Double Strings

题目链接

只需要两个拼起来 不需要多个

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<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
string s[maxn];
map<string,int>mp;
int find_ans(string s0, int len){
string t=""; t+=s0[0];
for(int i=1; i<len; ++i){
string s1=s0.substr(i);
if(mp.count(t)&&(mp.count(s1))) return 1;
t+=s0[i];
}
return 0;
}
int cmp(int a, int b){
return s[a].size()<s[b].size();
}
int solve(){
int n; cin>>n; mp.clear();
for(int i=0; i<n; ++i) cin>>s[i];
vector<int>ord(n),ans(n);
for(int i=0; i<n; ++i) ord[i]=i;
sort(ord.begin(),ord.end(),cmp);
int len0=s[ord[0]].size(),ff(0);
for(int i=0; i<n; ++i){
mp[s[ord[i]]]++; int len=s[ord[i]].size();
if(!ff&&len==len0) ans[ord[i]]=0;
else ff++,ans[ord[i]]=find_ans(s[ord[i]],len);
}
for(int i=0; i<n; ++i) cout<<ans[i];
return printf("\n");
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1703E: Mirror Grid

题目链接

美团笔试出过 秋招的小朋友可以看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
string s[maxn];
int solve(){
int n,ans(0); cin>>n;
for(int i=0; i<n; ++i) cin>>s[i];
for(int i=0; i<n; ++i) for(int j=0; j<n; ++j){
int tmp=(int)s[i][j]+s[j][n-i-1]+s[n-i-1][n-j-1]+s[n-j-1][i]-4*'0';
if(tmp<=2) s[i][j]=s[j][n-i-1]=s[n-i-1][n-j-1]=s[n-j-1][i]='0';
else s[i][j]=s[j][n-i-1]=s[n-i-1][n-j-1]=s[n-j-1][i]='1';
ans+=min(tmp, 4-tmp);
}
return printf("%d\n", ans);
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1703F: Yet Another Problem About Pairs Satisfying an Inequality

嘴完待补

1703G: Good Key, Bad Key

嘴完待补

1702A: Round Down the Price

题目链接

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
int n; scanf("%d", &n);
long long d=1; while(d<=n) d*=10;
return printf("%d\n", n-d/10);
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1702B: Polycarp Writes a String from Memory

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
string s;
cin>>s;
set<char>st;
int ans(0);
for(char c: s){
st.insert(c);
if(st.size()==4){
st.clear();
st.insert(c);
ans++;
}
}
if(st.size()) ans++;
return printf("%d\n",ans);
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1702C: Train and Queries

题目链接

离散化后存一个pair记录最远和最近

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
int n,k; scanf("%d%d", &n,&k);
vector<int>arr(n+1);
map<int,pair<int,int>>pos;
for(int i=1; i<=n; ++i){
scanf("%d", &arr[i]);
if(!pos.count(arr[i])) pos[arr[i]]={i,i};
else pos[arr[i]].second=i;
}
for(int i=0; i<k; ++i){
int a,b; scanf("%d%d", &a,&b);
if(!pos.count(a)||!pos.count(b)) puts("NO");
else puts(pos[b].second>pos[a].first?"YES":"NO");
}
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1702D: Not a Cheap String

题目链接

简单贪心

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
char s[maxn];
int cmp(int a,int b){
return s[a]<s[b];
}
int solve(){
int k; scanf("%s%d", s,&k);
int len=strlen(s),sum(0),cnt=len;
vector<int>arr(len);
for(int i=0; i<len; ++i) arr[i]=i;
sort(arr.begin(),arr.end(),cmp);
for(int i=0; i<len; ++i) sum+=s[i]-'a'+1;
for(int i=len-1; i>=0; --i){
if(sum<=k) break;
sum-=s[arr[i]]-'a'+1;
cnt=i;
}
sort(arr.begin(),arr.begin()+cnt);
for(int i=0; i<cnt; ++i) putchar(s[arr[i]]);
return putchar('\n');
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1702E: Split Into Two Sets

题目链接

找环,需要环不是奇数

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 = 2e5 + 5;
int n,ff,vis[maxn];
vector<int>vv[maxn];
set<int>ss;
void dfs(int st, int fa){
vis[st]++;
ss.insert(st);
if(vis[st]==2){
ff=!(ss.size()&1);
return;
}
if(!ff) return;
for(int i=0; i<vv[st].size(); ++i){
int num=vv[st][i];
if(num==fa) continue;
dfs(num, st);
}
}
int solve(){
scanf("%d", &n); ff=1;
vector<int>cnt(n+1);
for(int i=0; i<n; ++i){
int a,b; scanf("%d%d", &a,&b);
if(a==b) ff=0;
cnt[a]++; cnt[b]++;
if(cnt[a]>2||cnt[b]>2) ff=0;
if(!ff) continue;
vv[a].push_back(b);
vv[b].push_back(a);
}
for(int i=1;i<=n;++i)
if(!vis[i]){
ss.clear();
ss.insert(i);
dfs(i,0);
}
for(int i=1; i<=n; ++i)
vis[i]=0, vv[i].clear();
return puts(ff?"YES":"NO");
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1702F: Equate Multisets

题目链接

暴力过了(……)加了个小剪枝 可能是假的 反正过了(摊手)

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int solve(){
int n; scanf("%d", &n);
map<int,int>s1;
for(int i=0; i<n; ++i){
int a; scanf("%d", &a);
s1[a]++;
}
for(int i=0; i<n; ++i){
int b,b1; scanf("%d", &b);
if(i>1e5&&s1.size()>1e5) continue;
b1=b; while(b1){
int b2=b1;
while(b2<=(--s1.end())->first){
if(s1.count(b2)){
s1[b2]--;
if(!s1[b2]) s1.erase(b2);
b2=-1;
break;
}
b2*=2;
}
if(b2==-1) break;
if(s1.count(b1)){
s1[b1]--;
if(!s1[b1]) s1.erase(b1);
break;
}
b1/=2;
}
}
return puts(s1.size()||s1.size()>1e4?"NO":"YES");
}
int main(){
int _; scanf("%d",&_); while(_--) solve();
}

1702G1&G2: Passable Paths

已嘴待补

其他

我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=19q8g0m4dwk3l