【Codeforces 584C】Marina and Vasya
and Codeforces
2023-09-14 09:03:44 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
设cnt表示s1和s2不同的字符的个数 如果cnt>2*t 因为这cnt个位置肯定至少有一边不同 显然肯定会有一个f(s,S)的值大于t的 如果t<=cnt<=2*t 这种情况,不能全都让这cnt个位置s1和s2都与所求s不同 因为每个都会多出来cnt-t个 我们可以这样,从cnt中选出来cnt-t个位置,只让s1与s不同 然后再求出来cnt-t个位置,只让s2与s不同 这样f(s1,S)和f(s2,S)的值都为cnt-t了 还剩下cnt-(cnt-t)*2 =-cnt+2*t个不同的位置 让这些位置s1,s2的字符都跟S不同 那么f(s1,S)和f(s2,S)的值就都加上-cnt+2*t了 也即变成cnt-t+-cnt+2*t=t 刚好符合题意 (就是想办法把多余的部分抵消掉) cnt【代码】
import java.io.*;
import java.util.*;
public class Main {
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
//InputStream ins = new FileInputStream("E:\\rush.txt");
InputStream ins = System.in;
in = new InputReader(ins);
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static int N = 50000;
static class Task{
int n,t;
String s1,s2;
StringBuilder sb;
int cnt = 0;
public char v(char x,char y) {
for (char key = 'a';key<='z';key++){
if (key!=x && key!=y) return key;
}
return '2';
}
public void solve(InputReader in,PrintWriter out) {
n = in.nextInt();t = in.nextInt();
s1 = in.next();s2 = in.next();
for (int i = 0;i < n;i++) {
if (s1.charAt(i)!=s2.charAt(i)) {
cnt++;
}
}
if (cnt>2*t) {
out.println(-1);
return;
}
if (cnt>=t) {
int num = cnt-t;
int cl = 0;
for (int i = 0;i < n;i++) {
if (s1.charAt(i)==s2.charAt(i)) {
out.print(s1.charAt(i));
}else {
cl++;
if (cl<=num) {
out.print(s2.charAt(i));
}else if (cl>num && cl <=2*num) {
out.print(s1.charAt(i));
}else {
out.print(v(s1.charAt(i),s2.charAt(i)));
}
}
}
}else {
int num = t-cnt;
for (int i = 0;i < n;i++) {
if (s1.charAt(i)==s2.charAt(i)) {
if (num>0) {
num--;
out.print(v(s1.charAt(i),s2.charAt(i)));
}else {
out.print(s1.charAt(i));
}
}else {
out.print(v(s1.charAt(i),s2.charAt(i)));
}
}
}
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream ins) {
br = new BufferedReader(new InputStreamReader(ins));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
="">
相关文章
- RMAN-03002, RMAN-06059, ORA-19625 and ORA-27037 When Running RMAN Backup of Archivelogs
- [Java Spring Data] Query method clauses and expressions
- [Typescript] Performance Bundling and tslib
- [Tools] Scroll, Zoom, and Highlight code in a mdx-deck slide presentation with Code Surfer <🏄/>
- [D3JS] Add more map layer and color
- [Angular 2] Using ngrx/store and Reducers for Angular 2 Application State
- [CSS3] Parent relative and child absoulte
- [HTML 5] Access form and elements
- [React] Preview and edit a component live with React Live
- CRM WebUI and Hybris的Product页面标题实现
- Atitit.atiRI 与 远程调用的理论and 设计
- Atitit.实现反向代理(1)----url rewrite 配置and内容改写 and -绝对路径链接改写 java php
- 【Codeforces 1083A】The Fair Nut and the Best Path
- 【Codeforces 63C】Bulls and Cows
- 【Educational Codeforces Round 37 F】SUM and REPLACE
- 【Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined) D】Bash and a Tough Math Puzzle
- 【31.58%】【codeforces 719B】 Anatoly and Cockroaches
- 【29.89%】【codeforces 734D】Anton and Chess
- 【13.77%】【codeforces 734C】Anton and Making Potions
- 【23.33%】【codeforces 557B】Pasha and Tea
- 【codeforces 785D】Anton and School - 2
- 【codeforces 789B】Masha and geometric depression
- 【codeforces 761C】Dasha and Password(贪心+枚举做法)
- 【codeforces 750C】New Year and Rating(做法2)
- 【codeforces 548B】Mike and Fun
- 【codeforces 752B】Santa Claus and Keyboard Check
- 【codeforces 510C】Fox And Names
- 【codeforces 508A】Pasha and Pixels
- 【codeforces 515B】Drazil and His Happy Friends
- 【Codeforces Round #435 (Div. 2) C】Mahmoud and Ehab and the xor
- 【codeforces 812C】Sagheer and Nubian Market
- 【codeforces 803E】Roma and Poker
- Using Qt to build an Omi App for iOS (and Android)
- Codeforces Round #252 (Div. 2) B. Valera and Fruits(模拟)
- 3GPP TS 29244-g30 中英文对照 | 5.22.3 With one PFCP association per SMF and UPF