前言
比赛链接：https://codeforces.com/contest/1650
A. Deletions of Two Adjacent Letters （签到+思维）
题意
给你一个字符串，我们有一个操作（可以操作无限次），每次能删除两个相邻元素，问你删到最后能不能只剩下字符 C
思路
我们将 S字符串中所有 c 的位置存储在一个 vector中，然后遍历这个vector如果发现至少有一个位置是一个奇数那么肯定能剩下 C ,否则就是不可能存在
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
ll ksm(ll a,ll b) {
ll ans = 1;
for(;b;b>>=1LL) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
ll lowbit(ll x){return -x & x;}
const int N = 2e6+10;
int t,n,m,q,a[N];
void slove(){
string s;
char c;
cin>>s>>c;
vector<int> v;
int n = s.size();
for(int i = 0;i < n; ++i) if(s[i] == c) v.push_back(i+1);
bool fg = false;
for(auto it: v)
if(it % 2 == 1) fg = true;
if(fg) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
slove();
}
return 0;
}
B. DIV + MOD（数学+构造）
题意
定义
f
a
(
x
)
=
x
/
a
+
x
?
m
o
d
?
a
f_a{(x)} = x/a + x \ mod \ a
fa?(x)=x/a+x?mod?a ，其中
x
/
a
x/a
x/a 向下取整，然后给定
l
l
l 和
r
r
r 区间范围，问你在这个区间范围的最大
f
a
(
x
)
f_a(x)
fa?(x)是多少，其中
a
a
a 的值给定
思路
注意这里当
a
=
1
a=1
a=1 的时候很特殊，直接返回
r
r
r 就好了否则我们是想尽可能凑出一个模后为
a
?
1
a-1
a?1 的数，如果我们发现凑不出来，说明我们的这个
[
l
,
r
]
[l,r]
[l,r] 区间就是小于
a
a
a 的，那么就输出
f
a
(
r
)
f_a(r)
fa?(r) 就好啦
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
ll ksm(ll a,ll b) {
ll ans = 1;
for(;b;b>>=1LL) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
ll lowbit(ll x){return -x & x;}
const int N = 2e6+10;
ll t;
void slove(){
ll l,r,a;
cin>>l>>r>>a;
if(a == 1) {
cout<<r<<endl;
return;
}
ll p = (r/a) * a - 1LL;
if(p < l) p = l;
ll ans = max(p/a + p % a,r/a+r%a);
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
slove();
}
return 0;
}
C. Weight of the System of Nested Segments（贪心）
题意
思路
我们通过观察发现，对于这个重叠线段来说，我们只需要从权重从小到大考虑即可，找到了权值
w
w
w 最小的
2
×
n
2\times n
2×n 个点，我们只需要对这些点再进行一个位置排序就好啦
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
ll ksm(ll a,ll b) {
ll ans = 1;
for(;b;b>>=1LL) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
ll lowbit(ll x){return -x & x;}
const int N = 2e6+10;
ll t,n,m,q,a[N];
struct Node{
ll w,loc,idx;
};
bool cmp1(Node a,Node b){
return a.w < b.w;
}
bool cmp2(Node a,Node b){
return a.loc < b.loc;
}
Node b[N],c[N];
void slove(){
cin>>n>>m;
for(ll i = 1;i <= m; ++i) {
cin>>b[i].loc>>b[i].w;
b[i].idx = i;
}
sort(b+1,b+1+m,cmp1);
ll l = 2 * n;
ll ans = 0;
for(ll i = 1;i <= l; ++i) {
c[i] = b[i];
ans += b[i].w;
}
sort(c+1,c+1+l,cmp2);
cout<<ans<<endl;
for(int i = 1;i <= n; ++i) {
cout<<min(c[i].idx,c[l - i + 1].idx)<<" "<<max(c[i].idx,c[l - i + 1].idx)<<endl;
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
slove();
}
return 0;
}
D. Twist the Permutation（模拟）
题意
思路
我们从结果倒推，因为我们发现后面归位后不影响前面的序列进行循环操作，那么我们首先要将
n
n
n 归位到第n位，我们会发现我们的循环操作变成了向左循环，假设我们用
b
[
i
]
b[i]
b[i] 记录当前的第
i
i
i 个元素的位置，那么我们当前归位的这一位
l
o
c
loc
loc 应该向左循环
b
[
l
o
c
]
%
l
o
c
b[loc] \% loc
b[loc]%loc 次，并且，小于
l
o
c
loc
loc 的所有数都需要向左循环
b
[
l
o
c
]
%
l
o
c
b[loc] \% loc
b[loc]%loc 次，那么我们的操作就是模拟啦，复杂度
O
(
N
2
)
O(N^2)
O(N2)
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
ll ksm(ll a,ll b) {
ll ans = 1;
for(;b;b>>=1LL) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
ll lowbit(ll x){return -x & x;}
const int N = 2e6+10;
int t,n,m,q,a[N],b[N],ans[N];
void slove(){
cin>>n;
for(int i = 1;i <= n; ++i) {
cin>>a[i];
b[a[i]] = i;
}
for(int i = n ;i >= 1; --i) {
ans[i] = b[i] % i;
for(int j = 1;j <= n; ++j) {
b[j] = (b[j]-ans[i] + i) % i;
if(b[j] == 0) b[j] = i;
}
}
for(int i = 1;i <= n; ++i)
cout<<ans[i]<<" \n"[i == n];
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
slove();
}
return 0;
}
E. Rescheduling the Exam（）
明天起来写，先睡了
题意
思路
代码
|