此处将为大家介绍关于【CodeforcesRound1129】[AlexLopashevThanks-Round](Div.1)的详细内容，并且为您解答有关codegeass:zoftherecapt
此处将为大家介绍关于【Codeforces Round 1129】[Alex Lopashev Thanks-Round] (Div. 1)的详细内容，并且为您解答有关code geass:z of the recapture的相关问题，此外，我们还将为您介绍关于Codeforces 1104 D. Game with modulo-交互题-二分-woshizhizhang(Codeforces Round #534 (Div. 2))、Codeforces 1291 Round #616 (Div. 2) B、Codeforces Round #178 (Div. 2) B. Shaass and Bookshelf —— DP、Codeforces Round #224 (Div. 2)A. Ksenia and Pan Scales的有用信息。
本文目录一览：- 【Codeforces Round 1129】[Alex Lopashev Thanks-Round] (Div. 1)（code geass:z of the recapture）
- Codeforces 1104 D. Game with modulo-交互题-二分-woshizhizhang(Codeforces Round #534 (Div. 2))
- Codeforces 1291 Round #616 (Div. 2) B
- Codeforces Round #178 (Div. 2) B. Shaass and Bookshelf —— DP
- Codeforces Round #224 (Div. 2)A. Ksenia and Pan Scales
![【Codeforces Round 1129】[Alex Lopashev Thanks-Round] (Div. 1)（code geass:z of the recapture）](http://www.gvkun.com/zb_users/upload/2025/02/0beefa60-fae5-4f1d-b555-a10bca7b8a2e1739342565968.jpg "【Codeforces Round 1129】[Alex Lopashev Thanks-Round] (Div. 1)（code geass:z of the recapture）")
【Codeforces Round 1129】[Alex Lopashev Thanks-Round] (Div. 1)（code geass:z of the recapture）
Codeforces Round 1129
这场模拟比赛做了\(A1\)、\(A2\)、\(B\)、\(C\)，\(Div.1\)排名40。
\(A\)题是道贪心，可以考虑每一个站点是分开来的，把目的地最小编号的留到最后，所以答案稍微算一下就行了。
\(B\)题是道找规律，首先可以很容易地发现只要前面弄个负数的开头，错误算法就会忽略掉这一个值，所以利用这个来构造答案。（最讨厌构造题了）然后推导一番式子就会发现如果我们将第一个值放-1，则
\(\sum_{i=2}^na_i=k+n\)，
再更改一下形式（因为我们不知道n）
\(\sum_{i=2}^na_i-1=k+1\)。
然后就可以做出来了。
\(C\)题一眼不字符串吗，再一眼不dp吗，然后就写了个区间dp上去，发现没法判重了，就又写了个set装哈希值。。。（这里为下文的TLE作铺垫）把set改成哈希表，竟离奇MLE？？？改小一点数组就可以过辣。其实不难？
Codeforces 1104 D. Game with modulo-交互题-二分-woshizhizhang(Codeforces Round #534 (Div. 2))
This is an interactive problem.
Vasya and Petya are going to play the following game: Petya has some positive integer number aa. After that Vasya should guess this number using the following questions. He can say a pair of non-negative integer numbers (x,y)(x,y). Petya will answer him:
- "x", if (xmoda)≥(ymoda)(xmoda)≥(ymoda).
- "y", if (xmoda)<(ymoda)(xmoda)<(ymoda).
We define (xmoda)(xmoda) as a remainder of division xx by aa.
Vasya should guess the number aa using no more, than 60 questions.
It''s guaranteed that Petya has a number, that satisfies the inequality 1≤a≤1091≤a≤109.
Help Vasya playing this game and write a program, that will guess the number aa.
Your program should play several games.
Before the start of any game your program should read the string:
- "start" (without quotes) — the start of the new game.
- "mistake" (without quotes) — in the previous game, you found the wrong answer. Your program should terminate after reading this string and it will get verdict "Wrong answer".
- "end" (without quotes) — all games finished. Your program should terminate after reading this string.
After reading the string "start" (without quotes) the new game starts.
At the beginning, your program should ask several questions about pairs of non-negative integer numbers (x,y)(x,y). You can only ask the numbers, that satisfy the inequalities 0≤x,y≤2⋅1090≤x,y≤2⋅109. To ask a question print "? x y" (without quotes). As the answer, you should read one symbol:
- "x" (without quotes), if (xmoda)≥(ymoda)(xmoda)≥(ymoda).
- "y" (without quotes), if (xmoda)<(ymoda)(xmoda)<(ymoda).
- "e" (without quotes) — you asked more than 6060 questions. Your program should terminate after reading this string and it will get verdict "Wrong answer".
After your program asked several questions your program should print the answer in form "! a" (without quotes). You should print the number aa satisfying the inequalities 1≤a≤1091≤a≤109. It''s guaranteed that Petya''s number aa satisfied this condition. After that, the current game will finish.
We recall that your program can''t ask more than 6060 questions during one game.
If your program doesn''t terminate after reading "mistake" (without quotes), "end" (without quotes) or "e" (without quotes), it can get any verdict, because it will continue reading from closed input. Also, if your program prints answer or question in the incorrect format it can get any verdict, too. Be careful.
Don''t forget to flush the output after printing questions and answers.
To flush the output, you can use:
- fflush(stdout) in C++.
- System.out.flush() in Java.
- stdout.flush() in Python.
- flush(output) in Pascal.
- See the documentation for other languages.
It''s guaranteed that you should play at least 11 and no more than 100100 games.
Hacks:
In hacks, you can use only one game. To hack a solution with Petya''s number aa (1≤a≤1091≤a≤109) in the first line you should write a single number 11 and in the second line you should write a single number aa.
start
x
x
start
x
x
y
start
x
x
y
y
end? 0 0
? 10 1
! 1
? 0 0
? 3 4
? 2 5
! 2
? 2 4
? 2 5
? 3 10
? 9 1
! 3In the first test, you should play 33 games with Petya''s numbers 11, 22 and 33.
In the first game, Petya will answer "x" (without quotes) to any question, because (xmod1)=0(xmod1)=0 for any integer xx.
In the second game, if you will ask pair (0,0)(0,0), the answer will be "x" (without quotes), because (0mod2)≥(0mod2)(0mod2)≥(0mod2). But if you will ask pair (2,5)(2,5), the answer will be "y" (without quotes), because (2mod2)<(5mod2)(2mod2)<(5mod2), because (2mod2)=0(2mod2)=0 and (5mod2)=1(5mod2)=1.
题意就是猜数，通过x和y猜取模的数a，就类似于猜钱，假设我有钱，但是具体数量只有我知道，我的好友来猜，他说我的钱数在1块和2块之前，我说不对，然后猜在2块和4块之间，不对，然后。。。猜在50到100之间，对的，继续，在75到50之间，对的，然后继续，缩小范围，最后就找到了。就是二分的思路。
我写的时候wa了一面交题记录。。。各种错误，二分太挫了，最后发现是初始值放错位置了，这还写什么鬼代码。。。
代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn=1e5+10;
5
6 int main()
7 {
8 char ch[10],op[5];
9 while(cin>>ch){
10 if(ch[0]!=''s'') break;
11 ll x=1,y=2;
12 while(true){
13 cout<<"? "<<x<<" "<<y<<endl;
14 cin>>op;
15 if(op[0]==''x'') break;
16 x=y,y=y*2;
17 }
18 ll l=x,r=y,mid;
19 while(l<r-1){
20 mid=(l+r)>>1;
21 cout<<"? "<<mid<<" "<<l<<endl;
22 cin>>op;
23 if(op[0]==''x'') l=mid;
24 else r=mid;
25 }
26 cout<<"? "<<r<<" "<<l<<endl;
27 cin>>op;
28 if(op[0]==''x'') cout<<"! "<<l<<endl;
29 else cout<<"! "<<r<<endl;
30 fflush(stdout);
31 }
32 return 0;
33 }
...
Codeforces 1291 Round #616 (Div. 2) B
B. Array Sharpening
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You’re given an array a1,…,an of n non-negative integers.
Let’s call it sharpened if and only if there exists an integer 1≤k≤n such that a1<a2<…ak+1>…>an. In particular, any strictly increasing or strictly decreasing array is sharpened. For example:
The arrays [4], [0,1], [12,10,8] and [3,11,15,9,7,4] are sharpened;
The arrays [2,8,2,8,6,5], [0,1,1,0] and [2,5,6,9,8,8] are not sharpened.
You can do the following operation as many times as you want: choose any strictly positive element of the array, and decrease it by one. Formally, you can choose any i (1≤i≤n) such that ai>0 and assign ai:=ai−1.
Tell if it’s possible to make the given array sharpened using some number (possibly zero) of these operations.
Input
The input consists of multiple test cases. The first line contains a single integer t (1≤t≤15 000) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤3⋅105).
The second line of each test case contains a sequence of n non-negative integers a1,…,an (0≤ai≤109).
It is guaranteed that the sum of n over all test cases does not exceed 3⋅105.
Output
For each test case, output a single line containing “Yes” (without quotes) if it’s possible to make the given array sharpened using the described operations, or “No” (without quotes) otherwise.
Example
inputCopy
10
1
248618
3
12 10 8
6
100 11 15 9 7 8
4
0 1 1 0
2
0 0
2
0 1
2
1 0
2
1 1
3
0 1 0
3
1 0 1
outputCopy
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
Note
In the first and the second test case of the first test, the given array is already sharpened.
In the third test case of the first test, we can transform the array into [3,11,15,9,7,4] (decrease the first element 97 times and decrease the last element 4 times). It is sharpened because 3<11<15 and 15>9>7>4.
In the fourth test case of the first test, it’s impossible to make the given array sharpened.
这个题考虑不能构成的情况，就是从这数左边不能构成，右边也不能构成。然后左右都可以的时候，中间两个可能相等不能构成左右。
#include <bits/stdc++.h>
using namespace std;
int a[300010];
int main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin>>n;
bool bk = true;
for (int i = 1; i <= n; i++)
cin>>a[i] ;
for (int i = 1; i <= n; i++)
if (a[i] < min(i - 1, n - i))
{
bk = false;
break;
}
if (n % 2 == 0 && max(a[n / 2], a[n / 2 + 1]) < n / 2)
{
bk = false;
}
if (bk == false)
puts("No");
else
puts("Yes");
}
return 0;
}
Codeforces Round #178 (Div. 2) B. Shaass and Bookshelf —— DP
总结
以上是小编为你收集整理的Codeforces Round #178 (Div. 2) B. Shaass and Bookshelf —— DP全部内容。
如果觉得小编网站内容还不错，欢迎将小编网站推荐给好友。
Codeforces Round #224 (Div. 2)A. Ksenia and Pan Scales
Input The first line has a non-empty sequence of characters describing the scales. In this sequence, an uppercase English letter indicates a weight, and the symbol | indicates the delimiter (the character occurs in the sequence exactly onc
Input
The first line has a non-empty sequence of characters describing the scales. In this sequence, an uppercase English letter indicates a weight, and the symbol "|" indicates the delimiter (the character occurs in the sequence exactly once). All weights that are recorded in the sequence before the delimiter are initially on the left pan of the scale. All weights that are recorded in the sequence after the delimiter are initially on the right pan of the scale.
The second line contains a non-empty sequence containing uppercase English letters. Each letter indicates a weight which is not used yet.
It is guaranteed that all the English letters in the input data are different. It is guaranteed that the input does not contain any extra characters.
今天关于【Codeforces Round 1129】[Alex Lopashev Thanks-Round] (Div. 1)和code geass:z of the recapture的讲解已经结束，谢谢您的阅读，如果想了解更多关于Codeforces 1104 D. Game with modulo-交互题-二分-woshizhizhang(Codeforces Round #534 (Div. 2))、Codeforces 1291 Round #616 (Div. 2) B、Codeforces Round #178 (Div. 2) B. Shaass and Bookshelf —— DP、Codeforces Round #224 (Div. 2)A. Ksenia and Pan Scales的相关知识，请在本站搜索。
本文标签：
