彩笔光荣垫底。完成了两道题，第三道题WA，成功叉掉一个人。最后历史性的没有掉rating了！！！！多了32分！当前1234！暂时接触了掉newbie的危险
但是这次rank并不是很高，并没有创造出历史最好成绩，但是也算低谷期的小突破了！
A. Minimum Binary Number
Description
给你一个“01”串，你可以对其有两种以下的操作：
- 任意交换相邻两个字符
- '11'可替代为'1'
求经过变换后，能得到最小的二进制形式下的数（不含有前导0）
Input
The first line contains integer number n \((1 ≤ n ≤ 100)\) — the length of string s.
The second line contains the string s consisting of characters "0" and "1". It is guaranteed that the string s is correct.
Output
Print one string — the minimum correct string that you can obtain from the given one.
Examples
input
4
1001output
100input
1
1output
1Solution
做这道题的时候脑子也是很抽，没有反应过来replace后的1还能继续合并……然后交上去WA掉了，浪费了时间，还好最后及时想透AC
#include <cstdio>
int N;
char s;
int main(){
scanf("%d\n",&N);
int count = 0;
int zero = 0;
for(register int i=1;i<=N;++i){
s=getchar();
if(s=='1')count++;
else if(s=='0')zero++;
}
if(count==0){//如果字符串没有一个1，那就只能输出一个0
putchar('0');
return 0;
}
putchar('1');//不管它有几个1，最后都会合并成一个
for(register int i=1;i<=zero;++i)putchar('0');//0只能放在最后
return 0;
}B. Lara Croft and the New Game
Description
如图所示，先从左上角\((1,1)\)这个点往下走到\((n,1)\)，然后开始蛇形走位，即一直向右走到头，然后向上一个，在向左走到头（第一列不能走），再向上走一个，向右走到头……
问走到第\(K\)次时的位置坐标。
Input
The only line contains three integers n, m and k \((2 ≤ n, m ≤ 109, n is always even, 0 ≤ k < n·m)\). Note that k doesn't fit into 32-bit integer type!
Output
Print the cell (the row and the column where the cell is situated) where Lara ends up after she moves k times.
Examples
input
4 3 0output
1 1input
4 3 11output
1 2input
4 3 7output
3 2Solution
Naive solution would be just simulate the tranversal and break when k steps are made. Obviously, this won't fit into time limit. Then we can decompose the path to some parts which can be calculated separately.
Walk from the top left to the bottom left corner;
Walk from second column to m-th on even rows;
Walk from m-th column to second on odd rows.
If k < n then it's the first part. Otherwise you can use the fact that rows are of the same length. (k - n)div(m - 1) will tell you the row and (k - n)mod(m - 1) will get you the number of steps Lara have made along this row.
Overall complexity: O(1).
官方题解
这道题很明显是要推公式。并且并不是很难推，所以不写推导过程（写不出来）
// std
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n, m;
long long k;
int main() {
scanf("%d%d%lld", &n, &m, &k);
if (k < n){
printf("%lld 1\n", k + 1);
return 0;
}
k -= n;
long long row = k / (m - 1);
printf("%lld ", n - row);
if (row & 1)
printf("%lld\n", m - k % (m - 1));
else
printf("%lld\n", k % (m - 1) + 2);
return 0;
}//My Solution
#include <cstdio>
int main(){
long long N,M,k;
scanf("%I64d%I64d%I64d",&N,&M,&k);
if(k<N){
printf("%I64d 1",k+1);
return 0;
}
long long x,y;
x = k-N+1;
long long a = x/(M-1);
if(a*(M-1)==x)x = a;
else x = a+1;
x = N-x+1;
bool flag;
if((x&1)==(N&1))flag=true;
else flag=false;
a = (k-N+1)%(M-1);
if(flag){
y = a==0?M:a+1;
}
else {
y = a==0?2:M-a+1;
}
printf("%I64d %I64d",x,y);
return 0;
}Hack
不知道为什么看到一位小哥推了一半的公式，然后还有一半纯模拟……
于是就造了个大数据去卡他TLE，成功！
The hack is manual
Solution verdict:
TIME_LIMIT_EXCEEDED
Checker:
Input:
1000000000 1000000000 1999999998
Output:
Answer:
Time:
2000
Memory:
3497984C. Nested Segments
Description
有\(n\)组\((L,R)\)，对于任意一个\(i\)和\(j\)，若满足\(Li≤Lj\)和\(Rj≤Ri\)，则可以作为一个答案输出。
请输出任意满足条件的一组\(i,j\)，如果没有一个可行的答案请输出"-1 -1"
Input
The first line contains one integer $n (1 ≤ n ≤ 3·10^5) $— the number of segments.
Each of the next n lines contains two integers \(Li\) and \(Ri (1 ≤Li ≤ Ri ≤ 10^9)\) — the i-th segment.
Output
Print two distinct indices i and j such that segment ai lies within segment aj. If there are multiple answers, print any of them. If no answer exists, print -1 -1.
Example
input
5
1 10
2 9
3 9
2 3
2 9output
2 1input
3
1 5
2 6
6 20output
-1 -1Note
In the first example the following pairs are considered correct:
- \((2, 1), (3, 1), (4, 1), (5, 1)\) — not even touching borders;
- \((3, 2), (4, 2), (3, 5), (4, 5)\) — touch one border;
- \((5, 2), (2, 5)\) — match exactly.
Solution
当时是直接WA掉了……
#include <cstdio>
#include <algorithm>
#define MAXN 300005
struct Node{
int l,r,num;
}G[MAXN];
int N;
inline bool cmp(Node a,Node b){
if(a.l!=b.l)return a.l<b.l;
return a.r>b.r;
return false;
}
int main(){
scanf("%d",&N);
for(register int i=1;i<=N;++i){
scanf("%d%d",&G[i].l,&G[i].r);
G[i].num = i;
}
std::sort(G+1,G+1+N,cmp);
int Max = 0;
int ans = 0;
for(register int i=1;i<=N;++i){
if(G[i].r>Max)Max=G[i].r,ans=G[i].num;
else{
printf("%d %d",G[i].num,ans);
return 0;
}
}
puts("-1 -1");
return 0;
}idea
按L从小到大排序，L相同则按R从大到小排序。这样就保证了j一定会小于i
因为排在序列前的L一定更小，所以每次只需要记录当前最大的R，然后与后面的比较即可。