4题 （E题一开始初始化成负无穷了，急急急急急急急急急急急急急急急急急急
A
https://atcoder.jp/contests/abc342/tasks/abc342_a
模拟
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 i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define int long long
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
void solve(){
string s;cin>>s;
vector<int>v(26);
for(int i=0;i<s.size();i++){
v[s[i]-'a']++;
}
char c;
rep(i,0,25){
if(v[i]==1){
c='a'+i;
}
}
for(int i=0;i<s.size();i++){
if(s[i]==c){
cout<<i+1;
return;
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
B
https://atcoder.jp/contests/abc342/tasks/abc342_b
map一下（其实可以直接暴力，但是更低的时间复杂度肯定更好
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 i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define int long long
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
void solve(){
string s;cin>>s;
vector<int>v(26);
for(int i=0;i<s.size();i++){
v[s[i]-'a']++;
}
char c;
rep(i,0,25){
if(v[i]==1){
c='a'+i;
}
}
for(int i=0;i<s.size();i++){
if(s[i]==c){
cout<<i+1;
return;
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
C
https://atcoder.jp/contests/abc342/tasks/abc342_c
只换一次，记录，输出时改变就可以，有点类似并查集merge的思想
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
| #include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define int long long
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
void solve(){
int n;cin>>n;
string s;cin>>s;
int q;cin>>q;
vector<int>cnt(26);
iota(cnt.begin(),cnt.end(),0);
while(q--){
char c,d;cin>>c>>d;
rep(i,0,25){
if(cnt[i]==c-'a')cnt[i]=d-'a';
}
}
for(int i=0;i<s.size();i++){
cout<<char('a'+cnt[s[i]-'a']);
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
D
https://atcoder.jp/contests/abc342/tasks/abc342_d
很典的一道题，考虑唯一分解定理，只要质因数个数为偶数就可以
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
|
#include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define int long long
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
map<int,int>mp;
void solve(){
int n;cin>>n;
int ans=0;
rep(i,1,n){
int x;cin>>x;
for(int j=2;j*j<=x;j++){
while(x%(j*j)==0)x/=(j*j);
}
mp[x]++;
}
for(const auto &[x,y]:mp){
if(x==0)ans+=(y-1)*y/2ll+y*(n-y);
else ans+=y*(y-1)/2ll;
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
E
https://atcoder.jp/contests/abc342/tasks/abc342_e
f(N)初始化为0
这题很明显需要从后向前考虑
如果知道u的后驱v的f(v)，那么f(u)=max(min(k-1,(f[v]-c-l)/d)*d+l);
考虑这个公式，用一个优先队列bfs或者一个堆优化dijkstra都可以在nlogn内解决
这里需要注意初始化，虽然是可达性问题但是不可以初始化为-inf，否则会导致优先队列的比较出现问题，否则要写很多判断很麻烦
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
| #include<bits/stdc++.h>
using i64=long long;
#define int long long
#define rep(i,a,n) for(i64 i=(a);i<=(n);++i)
#define per(i,a,n) for(i64 i=(n);i>=(a);--i)
#define mst(a,x) memset(a,x,sizeof(a))
const int INF=0x3f3f3f3f,N=2e5+10;
using namespace std;
struct p{
i64 l,d,k,c,v;
};
bool vis[N];
vector<p>g[N];
i64 f[N];
struct node{
i64 t,u;
bool operator<(const node &rhs)const{
return t<rhs.t;
}
};
priority_queue<node>q;
void bfs(){
while(q.size()){
i64 u=q.top().u;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto &[l,d,k,c,v]:g[u]){
i64 t=f[u]-c;
i64 x=(t-l)/d;
x=min(k-1,x);
if(x*d+l>f[v]){
q.push({f[v]=x*d+l,v});
}
}
}
}
void solve(){
i64 n,m;cin>>n>>m;
while(m--){
i64 l,d,k,c,a,b;
cin>>l>>d>>k>>c>>a>>b;
g[b].push_back({l,d,k,c,a});
}
q.push({f[n]=9e18,n});
bfs();
rep(i,1,n-1){
if(f[i]==0ll){
cout<<"Unreachable\n";
}else{
cout<<f[i]<<'\n';
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
|
