1 second
256 megabytes
standard input
standard output
Little Chris is bored during his physics lessons (too easy), so he has built a toy box to keep himself occupied. The box is special, since it has the ability to change gravity.
There are n columns of toy cubes in the box arranged in a line. The i-th
column contains ai cubes.
At first, the gravity in the box is pulling the cubes downwards. When Chris switches the gravity, it begins to pull all the cubes to the right side of the box. The figure shows the initial and final configurations of the cubes in the box: the cubes that have
changed their position are highlighted with orange.
Given the initial configuration of the toy cubes in the box, find the amounts of cubes in each of the n columns after the gravity switch!
The first line of input contains an integer n (1 ≤ n ≤ 100),
the number of the columns in the box. The next line contains n space-separated integer numbers. The i-th
number ai (1 ≤ ai ≤ 100)
denotes the number of cubes in the i-th column.
Output n integer numbers separated by spaces, where the i-th
number is the amount of cubes in the i-th column after the gravity switch.
4 3 2 1 2
1 2 2 3
3 2 3 8
2 3 8
The first example case is shown on the figure. The top cube of the first column falls to the top of the last column; the top cube of the second column falls to the top of the third column; the middle cube of the first column falls to the top of the second column.
In the second example case the gravity switch does not change the heights of the columns.
A题一个快排就好了， 大的都到右边去了。。。
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[200];
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
sort (a, a + n);
printf("%d", a[0]);
for (int i = 1; i < n; i++)
printf(" %d", a[i]);
printf("\n");
}
return 0;
}
这次是出题最快的一次了。。。 12min
1 second
256 megabytes
standard input
standard output
Little Chris knows there's no fun in playing dominoes, he thinks it's too random and doesn't require skill. Instead, he decided to play withthe dominoes and make a "domino show".
Chris arranges n dominoes in a line, placing each piece vertically upright. In the beginning, he simultaneously pushes some of the dominoes either to the
left or to the right. However, somewhere between every two dominoes pushed in the same direction there is at least one domino pushed in the opposite direction.
After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right. When a vertical domino has dominoes falling on it from both sides,
it stays still due to the balance of the forces. The figure shows one possible example of the process.
Given the initial directions Chris has pushed the dominoes, find the number of the dominoes left standing vertically at the end of the process!
The first line contains a single integer n (1 ≤ n ≤ 3000),
the number of the dominoes in the line. The next line contains a character strings of length n.
The i-th character of the string si is
equal to
- "L", if the i-th domino has been pushed to the left;
- "R", if the i-th domino has been pushed to the right;
- ".", if the i-th domino has not been pushed.
It is guaranteed that if si = sj = "L"
and i < j, then there exists such k that i < k < j and sk = "R";
if si = sj = "R"
and i < j, then there exists such k that i < k < j and sk = "L".
Output a single integer, the number of the dominoes that remain vertical at the end of the process.
14 .L.R...LR..L..
4
5 R....
0
1 .
1
The first example case is shown on the figure. The four pieces that remain standing vertically are highlighted with orange.
In the second example case, all pieces fall down since the first piece topples all the other pieces.
In the last example case, a single piece has not been pushed in either direction.
B题各种想啊，先后写了两个思路，分类讨论太多，推了，当时想遍历一次字符数组解决问题，其实遍历两次问题就会简单很多。。。
然后找了一个简单的大神代码，如下：
大神的思想 如果有R, 向右推 ； 如果有L,向左推；并计算L，R中间的点到L,R的距离（矢量），如果L,R之间有奇数个点，则L,R中有且只有一点
的值为零。 （也不知道理解的对不对）(+﹏+)~狂晕
#include <string.h>
#include <stdio.h>
const int maxn = 3010;
char str[maxn];
int a[maxn];
int main()
{
int n, ans;
scanf("%d", &n);
scanf("%s", str);
memset(a, 0, sizeof(a));
for (int i = 0; i < n; i++)
{
if (str[i] == 'L')
for (int j = i; j >= 0; j--)
{
if (str[j] == 'R') break;
a[j] -= i - j + 1;
}
if (str[i] == 'R')
for (int j = i; j < n; j++)
{
if (str[j] == 'L') break;
a[j] += j - i + 1;
}
}
ans = 0;
for (int i = 0; i < n; i++)
{
if(!a[i]) ans++;
}
printf("%d\n", ans);
return 0;
}
1 second
256 megabytes
standard input
standard output
Little Chris is a huge fan of linear algebra. This time he has been given a homework about the unusual square of a square matrix.
The dot product of two integer number vectors x and y of
size n is the sum of the products of the corresponding components of the vectors. The unusual
square of an n × n square matrix A is
defined as the sum of n dot products. The i-th of
them is the dot product of the i-th row vector and the i-th
column vector in the matrix A.
Fortunately for Chris, he has to work only in GF(2)! This means that all operations (addition, multiplication) are calculated modulo 2. In fact, the matrix A is
binary: each element of A is either 0 or 1. For example, consider the following matrix A:
The unusual square of A is equal to (1·1 + 1·0 + 1·1) + (0·1 + 1·1 + 1·0) + (1·1 + 0·1 + 0·0) = 0 + 1 + 1 = 0.
However, there is much more to the homework. Chris has to process q queries; each query can be one of the following:
-
given a row index i, flip all the values in the i-th
row in A; -
given a column index i, flip all the values in the i-th
column in A; - find the unusual square of A.
To flip a bit value w means to change it to 1 - w,
i.e., 1 changes to 0 and 0 changes to 1.
Given the initial matrix A, output the answers for each query of the third type! Can you solve Chris's homework?
The first line of input contains an integer n (1 ≤ n ≤ 1000),
the number of rows and the number of columns in the matrix A. The next nlines
describe the matrix: the i-th line contains n space-separated
bits and describes the i-th row of A. The j-th
number of the i-th lineaij (0 ≤ aij ≤ 1)
is the element on the intersection of the i-th row and the j-th
column of A.
The next line of input contains an integer q (1 ≤ q ≤ 106),
the number of queries. Each of the next q lines describes a single query, which can be one of the following:
- 1 i — flip the values of the i-th row;
- 2 i — flip the values of the i-th column;
- 3 — output the unusual square of A.
Note: since the size of the input and output could be very large, don't use slow output techniques in your language. For example, do not use input and output streams (cin, cout) in C++.
Let the number of the 3rd type queries in the input be m. Output a single string s of
length m, where the i-th symbol of s is
the value of the unusual square of A for the i-th
query of the 3rd type as it appears in the input.
3 1 1 1 0 1 1 1 0 0 12 3 2 3 3 2 2 2 2 1 3 3 3 1 2 2 1 1 1 3
01001
给了一个矩阵，GF(2):GF是Galois Field的缩写,中文称其为Galois域或有限域,GF（2）是最简单的有限域，只有0,1二元及+（异或运算）、×（与运算）。然后给了一个操作数n， 之后是n个操作： 1 i 代表翻转第i行 0变1 ，1 变0； 2 i代表翻转第i列 ，同上；3代表求矩阵的值；
#include <stdio.h>
const int N = 1000 + 10;
int a[N][N];
int main()
{
int n, qn, q1, q2;
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &a[i][j]);
int ans = 0;
for(int i = 0; i < n; i++)
ans += a[i][i];
scanf("%d", &qn);
while (qn--) {
scanf("%d", &q1);
if (q1 == 3) { ans &= 1; printf("%d", ans); }
else { scanf("%d", &q2); ++ans; }
}
return 0;
}