针对CodeforcesRound#599(Div.2)B1.CharacterSwap(EasyVersion)水题这个问题，本篇文章进行了详细的解答，同时本文还将给你拓展A.CreatingaCh
针对Codeforces Round #599 (Div. 2) B1. Character Swap (Easy Version) 水题这个问题，本篇文章进行了详细的解答，同时本文还将给你拓展A. Creating a Character（Educational Codeforces Round 72 (Rated for Div. 2) ）、cf1008 codeforces round #535(div3) E1. Array and Segments (Easy version)、Codeforces 1082 A. Vasya and Book - 题意 (Educational Codeforces Round 55 (Rated for Div. 2))、Codeforces 1254B1 - Send Boxes to Alice (Easy Version)等相关知识，希望可以帮助到你。
本文目录一览：- Codeforces Round #599 (Div. 2) B1. Character Swap (Easy Version) 水题
- A. Creating a Character（Educational Codeforces Round 72 (Rated for Div. 2) ）
- cf1008 codeforces round #535(div3) E1. Array and Segments (Easy version)
- Codeforces 1082 A. Vasya and Book - 题意 (Educational Codeforces Round 55 (Rated for Div. 2))
- Codeforces 1254B1 - Send Boxes to Alice (Easy Version)
Codeforces Round #599 (Div. 2) B1. Character Swap (Easy Version) 水题
B1. Character Swap (Easy Version)
This problem is different from the hard version. In this version Ujan makes exactly one exchange. You can hack this problem only if you solve both problems.
After struggling and failing many times, Ujan decided to try to clean up his house again. He decided to get his strings in order first.
Ujan has two distinct strings and of length consisting of only of lowercase English characters. He wants to make them equal. Since Ujan is lazy, he will perform the following operation exactly once: he takes two positions and (1≤,≤, the values and can be equal or different), and swaps the characters and . Can he succeed?
Note that he has to perform this operation exactly once. He has to perform this operation.
Input
The first line contains a single integer (1≤≤10), the number of test cases.
For each of the test cases, the first line contains a single integer (2≤≤104), the length of the strings and .
Each of the next two lines contains the strings and , each having length exactly . The strings consist only of lowercase English letters. It is guaranteed that strings are different.
Output
For each test case, output "Yes" if Ujan can make the two strings equal and "No" otherwise.
You can print each letter in any case (upper or lower).
Example
input
4 5 souse houhe 3 cat dog 2 aa az 3 abc bca
output
Yes No No No
Note
In the first test case, Ujan can swap characters 1 and 4, obtaining the word "house".
In the second test case, it is not possible to make the strings equal using exactly one swap of and .
题意
现在给你两个字符串 s 和 t，然后你可以选择 i，j 两个位置，交换 s [i] 和 t [j]。问你在只交换一次的情况下，能不能使得两个字符串相同。
题解
我们遍历两个字符串，我们进行对比，看一共有多少个位置不同。
如果所有位置都相同，输出 yes
如果只有一个位置不同，那么一定是 no。
如果是两个位置不同，我们就暴力枚举交换 s [i],t [j] 还是 s [j] 和 t [i]。
其他情况都是 no
代码
#include<bits/stdc++.h>
using namespace std;
int n;
string s,t;
void solve(){
cin>>n;
cin>>s>>t;
vector<int>pos;
for(int i=0;i<s.size();i++){
if(s[i]!=t[i]){
pos.push_back(i);
}
}
if(pos.size()==0){
puts("YES");
}else if(pos.size()==1){
puts("NO");
}else if(pos.size()==2){
swap(s[pos[0]],t[pos[1]]);
if(s==t){
puts("YES");
return;
}
swap(s[pos[0]],t[pos[1]]);
swap(t[pos[0]],s[pos[1]]);
if(s==t){
puts("YES");
return;
}
puts("NO");
}else{
puts("NO");
}
}
int main(){
int t;
scanf("%d",&t);
while(t--)
solve();
}
A. Creating a Character（Educational Codeforces Round 72 (Rated for Div. 2) ）
You play your favourite game yet another time. You chose the character you didn‘t play before. It has strstr points of strength and intint points of intelligence. Also,at start,the character has expexp free experience points you can invest either in strength or in intelligence (by investing one point you can either raise strength by 11 or raise intelligence by 11).
Since you‘d like to make some fun you want to create a jock character,so it has more strength than intelligence points (resulting strength is strictly greater than the resulting intelligence).
Calculate the number of different character builds you can create (for the purpose of replayability) if you must invest all free points. Two character builds are different if their strength and/or intellect are different.
The first line contains the single integer TT (1≤T≤1001≤T≤100) — the number of queries. Next TT lines contain descriptions of queries — one per line.
This line contains three integers strstr, intint and expexp (1≤str,int≤1081≤str,int≤108, 0≤exp≤1080≤exp≤108) — the initial strength and intelligence of the character and the number of free points,respectively.
Print TT integers — one per query. For each query print the number of different character builds you can create.
4 5 3 4 2 1 0 3 5 5 4 10 6
3 1 2 0
In the first query there are only three appropriate character builds: (str=7,int=5)(str=7,int=5), (8,4)(8,4) and (9,3)(9,3). All other builds are either too smart or don‘t use all free points.
In the second query there is only one possible build: (2,1)(2,1).
In the third query there are two appropriate builds: (7,6)(7,6), (8,5)(8,5).
In the fourth query all builds have too much brains.
int main() { int cnt,n,m,k; while(cin>>n) { while(n--) { cin>>m>>k>>cnt; cout<<min( max( (m+cnt-k+1)/2,0 ),cnt+1 )<<endl; } } ok; }
cf1008 codeforces round #535(div3) E1. Array and Segments (Easy version)
这道题会发现如果一开始确定了整个序列中的最小值，就可以把所有包含他的区间都选上。因为如果最大值在区间内，则不会改变结果（最大值最小值都减一）
最大值不在区间内，正好使得最大值最小值的差变大。
所以枚举一下1到n，然后按照贪心策略跑一遍就好啦
#include<bits/stdc++.h>
using namespace std;
int a[310];
int b[310];
int l[310],r[310];
const int INF=(int)1e9+7;
vector<int> res,tmp;
int num;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d%d",&l[i],&r[i]);
for(int pos=1;pos<=n;pos++)
{
tmp.clear();
for(int i=1;i<=n;i++)
b[i]=a[i];
for(int i=1;i<=m;i++)
{
if(l[i]<=pos&&r[i]>=pos)
{
tmp.push_back(i);
for(int j=l[i];j<=r[i];j++)
{
b[j]--;
}
}
}
int maxn=-INF,minn=INF;
for(int i=1;i<=n;i++)
{
maxn=max(b[i],maxn);
minn=min(b[i],minn);
}
if(maxn-minn>num)
{
num=maxn-minn;
res=tmp;
}
}
printf("%d\n",num);
printf("%d\n",res.size());
for(int i=0;i<res.size();i++)
printf("%d ",res[i]);
printf("\n");
}
Codeforces 1082 A. Vasya and Book - 题意 (Educational Codeforces Round 55 (Rated for Div. 2))
Vasya is reading a e-book. The file of the book consists of nn pages, numbered from 11 to nn. The screen is currently displaying the contents of page xx, and Vasya wants to read the page yy. There are two buttons on the book which allow Vasya to scroll dd pages forwards or backwards (but he cannot scroll outside the book). For example, if the book consists of 1010 pages, and d=3d=3, then from the first page Vasya can scroll to the first or to the fourth page by pressing one of the buttons; from the second page — to the first or to the fifth; from the sixth page — to the third or to the ninth; from the eighth — to the fifth or to the tenth.
Help Vasya to calculate the minimum number of times he needs to press a button to move to page yy.
The first line contains one integer tt (1≤t≤1031≤t≤103) — the number of testcases.
Each testcase is denoted by a line containing four integers nn, xx, yy, dd (1≤n,d≤1091≤n,d≤109, 1≤x,y≤n1≤x,y≤n) — the number of pages, the starting page, the desired page, and the number of pages scrolled by pressing one button, respectively.
Print one line for each test.
If Vasya can move from page xx to page yy, print the minimum number of times he needs to press a button to do it. Otherwise print −1−1.
3
10 4 5 2
5 1 3 4
20 4 19 34
-1
5In the first test case the optimal sequence is: 4→2→1→3→54→2→1→3→5.
In the second test case it is possible to get to pages 11 and 55.
In the third test case the optimal sequence is: 4→7→10→13→16→194→7→10→13→16→19.
翻到头只能从头翻，翻到尾只能从尾倒着翻。
代码:
1 //A
2 #include<bits/stdc++.h>
3 using namespace std;
4 typedef long long ll;
5 const int maxn=1e5+10;
6 const int inf=0x3f3f3f3f;
7
8 int main()
9 {
10 int t;
11 cin>>t;
12 while(t--){
13 int n,x,y,d,ans=inf;
14 cin>>n>>x>>y>>d;
15 if(abs(y-x)%d==0) {ans=min(ans,abs(y-x)/d);}
16 if((y-1)%d==0) {ans=min(ans,x/d+(y-1)/d+(x%d==0?0:1));}
17 if((n-y)%d==0) {ans=min(ans,(n-x)/d+(n-y)/d+((n-x)%d==0?0:1));}
18 if(ans==inf) cout<<-1<<endl;
19 else cout<<ans<<endl;
20 }
21 }
Codeforces 1254B1 - Send Boxes to Alice (Easy Version)
题意
有$n(1\leq n\leq 10^5)$个盒子，每个盒子有$a_i(0\leq a_i \leq 1)$个糖果，你每一次可以将第$i$个盒子里的糖果放到第$i-1$或$i+1$个盒子中（如果盒子存在）。最后要使每个盒子的糖果数量都整除$k(k>1)$（注意盒子可以为空），问最小操作数。
分析
$(1)$因为糖果是类似于平铺的形式，堆叠时，我们可以发现所有存在糖果的盒子中数量均为$k$。若存在一个盒子中有$2*k$个糖果，在平铺到堆叠的过程中，将另外$k$个糖果分在更近的盒子能得到更小的答案。
$(2)$设糖果总数为$cnt$，所有存在糖果的盒子数量均为$k$，我们又可以发现，最小的操作是将$1$~$k$、$k+1$~$2k$、……、$i*k+1$~$(i+1)*k$放在一起，即将相邻的$k$个放在一堆。
$(3)$对于某$k$个糖果，需要找到一个盒子，这个盒子到这$k$个糖果的距离最小(kNN算法)。我们将糖果看成数轴上的点，运用高一的绝对值知识（我忘了，我向高中数学老师谢罪）。
- 若$k$为奇数，则将该盒子设置为最中间糖果所在的盒子
- 若$k$为偶数，则将该盒子设置为最中间两个糖果中任意一个所在的盒子
即对于$i*k+1$~$(i+1)*k$来说，第$k-i/2$个盒子，设其坐标为$ave$。
$(4)$为降低时间复杂度，我们采取前缀的思想，$sum[i]$表示坐标$i$之前的糖果的坐标总和（没糖果的盒子不加），$num[i]$表示坐标$i$之前有多少糖果。
$(5)$枚举可以被$cnt$整除的$k$，模拟$(2)$的过程，设$first$为第$i*k+1$个糖果的坐标，$last$为第$(i+1)*k$个糖果的坐标，那么每个循环都得加上$(num[ave] - num[first - 1])*ave-(sum[ave] - sum[first - 1])+(sum[last] - sum[ave])-(num[last] - num[ave])*ave$，意思为$ave$之前的操作次数加上$ave$之后的操作次数，最后取最小值
$(6)$记得开$long\ long$，$INF$也记得开大一点。
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define LL long long
#define pii pair<int,int>
#define int ll
using namespace std;
const int maxn = (ll) 1e5 + 5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f3f3f3f3f;
int a[maxn];
int cnt = 0;
int sum[maxn];
int num[maxn];
signed main() {
start;
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
num[i] = num[i - 1] + x;//前缀数量
if (x) {
a[++cnt] = i;
sum[i] = i;
}
}
for (int i = 1; i <= n; ++i)//前缀坐标和
sum[i] += sum[i - 1];
int ans = inf;
for (int i = 2; i <= cnt; ++i) {
if (cnt % i == 0) {
int tmp = 0;
for (int k = i; k <= cnt; k += i) {//k为最后的糖果
int first = a[k - i + 1];
int last = a[k];
int ave = a[k - i / 2];
int num1 = num[ave] - num[first - 1];
int num2 = num[last] - num[ave];
int tot1 = sum[ave] - sum[first - 1];
int tot2 = sum[last] - sum[ave];
int t = num1 * ave - tot1 + tot2 - num2 * ave;
tmp += t;
}
ans = min(ans, tmp);
}
}
if (ans == inf)
cout << -1;
else
cout << ans;
return 0;
}
今天关于Codeforces Round #599 (Div. 2) B1. Character Swap (Easy Version) 水题的分享就到这里，希望大家有所收获，若想了解更多关于A. Creating a Character（Educational Codeforces Round 72 (Rated for Div. 2) ）、cf1008 codeforces round #535(div3) E1. Array and Segments (Easy version)、Codeforces 1082 A. Vasya and Book - 题意 (Educational Codeforces Round 55 (Rated for Div. 2))、Codeforces 1254B1 - Send Boxes to Alice (Easy Version)等相关知识，可以在本站进行查询。
本文标签：
