String can be called correct if it consists of characters "0" and "1" and there are no redundant leading zeroes. Here are some examples: "0", "10", "1001".
You are given a correct string s.
You can perform two different operations on this string:
- swap any pair of adjacent characters (for example, "101"
"110");
- replace "11" with "1" (for example, "110"
Let val(s) be such a number that s is its binary representation.
Correct string a is less than some other correct string b iff val(a) < val(b).
Your task is to find the minimum correct string that you can obtain from the given one using the operations described above. You can use these operations any number of times in any order (or even use no operations at all).
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.
Print one string — the minimum correct string that you can obtain from the given one.
4 1001
100
1 1
1
In the first example you can obtain the answer by the following sequence of operations: "1001"
In the second example you can't obtain smaller answer no matter what operations you use.
A题就直接考虑情况，模拟一下就好了，多尝试几次自己出的样例
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <map>
#define EPS 1e-10
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char s[110];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",s);
int sum0=0,sum1=0;
for(int i=0;i<n;i++)
{
if(s[i]=='1') sum1++;
else if(s[i]=='0') sum0++;
}
if(sum1==0)
{
printf("0\n");
}
else if(sum0==0)
{
printf("1\n");
}
else if(sum1==1&&sum0!=0)
{
puts(s);
}
else if(sum0==1&&sum1!=0)
{
printf("10\n");
}
else {
printf("1");
for(int i=1;i<=sum0;i++)
{
printf("0");
}
printf("\n");
}
return 0;
}
You might have heard about the next game in Lara Croft series coming out this year. You also might have watched its trailer. Though you definitely missed the main idea about its plot, so let me lift the veil of secrecy.
Lara is going to explore yet another dangerous dungeon. Game designers decided to use good old 2D environment. The dungeon can be represented as a rectangle matrix of n rows and m columns. Cell (x, y) is the cell in the x-th row in the y-th column. Lara can move between the neighbouring by side cells in all four directions.
Moreover, she has even chosen the path for herself to avoid all the traps. She enters the dungeon in cell (1, 1), that is top left corner of the matrix. Then she goes down all the way to cell (n, 1) — the bottom left corner. Then she starts moving in the snake fashion — all the way to the right, one cell up, then to the left to the cell in 2-nd column, one cell up. She moves until she runs out of non-visited cells. n and mgiven are such that she always end up in cell (1, 2).
Lara has already moved to a neighbouring cell k times. Can you determine her current position?
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!
Print the cell (the row and the column where the cell is situated) where Lara ends up after she moves k times.
4 3 0
1 1
4 3 11
1 2
4 3 7
3 2
Here is her path on matrix 4 by 3:
那么B题的话，实际上是一道找规律的题目，就模拟一下找规律，重点是要注意讨论好K的范围与关系，下面就是我的理解与思考
k分是否为0和是否等于n*m-1和第三类进行分组讨论，然后找规律模拟即可
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <map>
#define EPS 1e-10
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
ll m,n,k;
scanf("%lld%lld%lld",&n,&m,&k);
if(k==0)
{
printf("1 1\n");
}
else if(k==m*n-1)
{
printf("1 2\n");
}
else if(k>0&&k<=n-1)
{
printf("%lld 1\n",k+1);
}
else
{
k=k-(n-1);
if(k<m)
{
printf("%lld %lld\n",n,k+1);
}
else if(k==m)
{
printf("%lld %lld\n",n-1,m);
}
else
{
k-=m;
ll x,y;
ll s=k/(m-1);
ll cnt=k%(m-1);
if(s%2==0)
{
x=n-1-s;
y=m-cnt;
}
else
{
x=n-1-s;
y=cnt+2;
}
printf("%lld %lld\n",x,y);
}
}
return 0;
}
You are given a sequence a1, a2, ..., an of one-dimensional segments numbered 1 through n. Your task is to find two distinct indices i and j such that segment ai lies within segment aj.
Segment [l1, r1] lies within segment [l2, r2] iff l1 ≥ l2 and r1 ≤ r2.
Print indices i and j. If there are multiple answers, print any of them. If no answer exists, print -1 -1.
The first line contains one integer n (1 ≤ n ≤ 3·105) — the number of segments.
Each of the next n lines contains two integers li and ri (1 ≤ li ≤ ri ≤ 109) — the i-th segment.
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.
5 1 10 2 9 3 9 2 3 2 9
2 1
3 1 5 2 6 6 20
-1 -1
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.
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <map>
#define EPS 1e-10
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef struct line{
int l,r,num;
}Line;
Line a[300010];
int cmp(Line a,Line b)
{
if(a.l!=b.l) return a.l<b.l;
else return a.r>b.r;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].num=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n-1;i++)
{
if(a[i].l<=a[i+1].l&&a[i].r>=a[i+1].r)
{
printf("%d %d\n",a[i+1].num,a[i].num);
return 0;
}
}
printf("-1 -1\n");
return 0;
}
由于本弱只会ABC签到题，做只能做到这里了...