A. Integer Points
time limit per test2 seconds memory limit per test512 megabytes
DLS and JLS are bored with a Math lesson. In order to entertain themselves, DLS took a sheet of paper and drew n distinct lines, given by equations \(y = x + p_i\) for some distinct \(p_1, p_2, \ldots, p_n\).
Then JLS drew on the same paper sheet m distinct lines given by equations \(y = -x + q_i\) for some distinct \(q_1, q_2, \ldots, q_m\).
DLS and JLS are interested in counting how many line pairs have integer intersection points, i.e. points with both coordinates that are integers. Unfortunately, the lesson will end up soon, so DLS and JLS are asking for your help.Input
The first line contains one integer t \((1 \le t \le 1000)\), the number of test cases in the input. Then follow the test case descriptions.
The first line of a test case contains an integer n \((1 \le n \le 10^5)\), the number of lines drawn by DLS.
The second line of a test case contains n distinct integers \(p_i (0 \le p_i \le 10^9)\) describing the lines drawn by DLS. The integer \(p_i\) describes a line given by the equation \(y = x + p_i\).
The third line of a test case contains an integer m \((1 \le m \le 10^5)\), the number of lines drawn by JLS.
The fourth line of a test case contains m distinct integers \(q_i (0 \le q_i \le 10^9)\) describing the lines drawn by JLS. The integer \(q_i\) describes a line given by the equation \(y = -x + q_i\).
The sum of the values of n over all test cases in the input does not exceed \(10^5\). Similarly, the sum of the values of m over all test cases in the input does not exceed \(10^5\).
In hacks it is allowed to use only one test case in the input, so t=1 should be satisfied.Output
For each test case in the input print a single integer — the number of line pairs with integer intersection points.
Exampleinput
3 3 1 3 2 2 0 3 1 1 1 1 1 2 1 1
output
3 1 0
Note
The picture shows the lines from the first test case of the example. Black circles denote intersection points with integer coordinates.
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,m,odd1,odd2,ev1,ev2;
void solve(){
odd1=odd2=ev1=ev2=0;
scanf("%d",&n);
rep(i,1,n){
int x;scanf("%d",&x);
if(x%2) odd1++;
else ev1++;
}
scanf("%d",&m);
rep(i,1,m){
int x;scanf("%d",&x);
if(x%2) odd2++;
else ev2++;
}
printf("%lld\n",1ll*odd1*odd2+1ll*ev1*ev2);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. Grow The Tree
time limit per test2 seconds memory limit per test512 megabytes
Gardener Alexey teaches competitive programming to high school students. To congratulate Alexey on the Teacher's Day, the students have gifted him a collection of wooden sticks, where every stick has an integer length. Now Alexey wants to grow a tree from them.
The tree looks like a polyline on the plane, consisting of all sticks. The polyline starts at the point (0, 0). While constructing the polyline, Alexey will attach sticks to it one by one in arbitrary order. Each stick must be either vertical or horizontal (that is, parallel to \(OX\) or \(OY\) axis). It is not allowed for two consecutive sticks to be aligned simultaneously horizontally or simultaneously vertically. See the images below for clarification.
Alexey wants to make a polyline in such a way that its end is as far as possible from (0, 0). Please help him to grow the tree this way.
Note that the polyline defining the form of the tree may have self-intersections and self-touches, but it can be proved that the optimal answer does not contain any self-intersections or self-touches.Input
The first line contains an integer n \((1 \le n \le 100\,000)\) — the number of sticks Alexey got as a present.
The second line contains n integers \(a_1, \ldots, a_n (1 \le a_i \le 10\,000)\) — the lengths of the sticks.Output
Print one integer — the square of the largest possible distance from (0, 0) to the tree end.
Examplesinput
3 1 2 3
output
26
input
4 1 1 2 2
output
20
Note
The following pictures show optimal trees for example tests. The squared distance in the first example equals \(5 \cdot 5 + 1 \cdot 1 = 26\), and in the second example \(4 \cdot 4 + 2 \cdot 2 = 20\).
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,a[maxn];
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]);
sort(a+1,a+1+n);
ll x=0,y=0;
int mid=n/2;
rep(i,1,mid) x+=a[i];
rep(i,mid+1,n) y+=a[i];
printf("%lld\n",x*x+y*y);
}
C. Ivan the Fool and the Probability Theory
time limit per test1 second memory limit per test512 megabytes
Recently Ivan the Fool decided to become smarter and study the probability theory. He thinks that he understands the subject fairly well, and so he began to behave like he already got PhD in that area.
To prove his skills, Ivan decided to demonstrate his friends a concept of random picture. A picture is a field of n rows and m columns, where each cell is either black or white. Ivan calls the picture random if for every cell it has at most one adjacent cell of the same color. Two cells are considered adjacent if they share a side.
Ivan's brothers spent some time trying to explain that it's not how the randomness usually works. Trying to convince Ivan, they want to count the number of different random (according to Ivan) pictures. Two pictures are considered different if at least one cell on those two picture is colored differently. Since the number of such pictures may be quite large, print it modulo \(10^9 + 7\).Input
The only line contains two integers n and m \((1 \le n, m \le 100\,000)\), the number of rows and the number of columns of the field.Output
Print one integer, the number of random pictures modulo \(10^9 + 7\).
Exampleinput
2 3
output
8
Note
The picture below shows all possible random pictures of size 2 by 3.
如果单独对于行分析的话就是一个斐波那契数列，扩展成列的话也是，那么就是一个横竖都是斐波那契数列的东西
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,m;
ll dp[maxn];
void precal(){
dp[1]=2;dp[2]=2;
rep(i,3,(int)1e5) dp[i]=(dp[i-1]+dp[i-2])%mod;
rep(i,2,(int)1e5) dp[i]=(dp[i]+dp[i-1])%mod;
}
int main(){
precal();
scanf("%d%d",&n,&m);
printf("%lld\n",(dp[n-1]+dp[m-1]+2)%mod);
}
D1. The World Is Just a Programming Task (Easy Version)
time limit per test1 second memory limit per test512 megabytes
This is an easier version of the problem. In this version, \(n \le 500\).
Vasya is an experienced developer of programming competitions' problems. As all great minds at some time, Vasya faced a creative crisis. To improve the situation, Petya gifted him a string consisting of opening and closing brackets only. Petya believes, that the beauty of the bracket string is a number of its cyclical shifts, which form a correct bracket sequence.
To digress from his problems, Vasya decided to select two positions of the string (not necessarily distinct) and swap characters located at this positions with each other. Vasya will apply this operation exactly once. He is curious what is the maximum possible beauty he can achieve this way. Please help him.
We remind that bracket sequence s is called correct if:
- s is empty;
- s is equal to "(t)", where t is correct bracket sequence;
- s is equal to \(t_1 t_2\), i.e. concatenation of \(t_1\) and \(t_2\), where \(t_1\) and \(t_2\) are correct bracket sequences.
For example, "(()())", "()" are correct, while ")(" and "())" are not.
The cyclical shift of the string s of length n by k \((0 \leq k < n)\) is a string formed by a concatenation of the last k symbols of the string s with the first n - k symbols of string s. For example, the cyclical shift of string "(())()" by 2 equals "()(())".
Cyclical shifts i and j are considered different, if \(i \ne j\).
Input
The first line contains an integer n \((1 \le n \le 500)\), the length of the string.
The second line contains a string, consisting of exactly n characters, where each of the characters is either "(" or ")".Output
The first line should contain a single integer — the largest beauty of the string, which can be achieved by swapping some two characters.
The second line should contain integers l and r \((1 \leq l, r \leq n)\) — the indices of two characters, which should be swapped in order to maximize the string's beauty.
In case there are several possible swaps, print any of them.
Examplesinput
10 ()()())(()
output
5 8 7
input
12 )(()(()())()
output
4 5 10
input
6 )))(()
output
0 1 1
Note
In the first example, we can swap 7-th and 8-th character, obtaining a string "()()()()()". The cyclical shifts by 0, 2, 4, 6, 8 of this string form a correct bracket sequence.
In the second example, after swapping 5-th and 10-th character, we obtain a string ")(())()()(()". The cyclical shifts by 11, 7, 5, 3 of this string form a correct bracket sequence.
In the third example, swap of any two brackets results in 0 cyclical shifts being correct bracket sequences.
只会简单版本，\(o(n^3)\)的算法，首先\(n^2\)枚举两个交换的点，再\(O(n)\)算出答案；具体讲一下如何算答案；
对于一个序列s，首先预处理出左右括号差值的前缀和c[i]；
再预处理出前缀最小值和后缀最小值；
判断一个串是否合法就是看这个串中所有的c[i]是否都非负
那么我们将一个前缀移到最后的话，假设那个前缀是\(s_1\)，后缀是\(s_2\)，那么对于\(s_2\)中的每个c的值都是要减去c[pos]的，其中pos为前缀的最后一个下标；
同样的对于前缀来说，所有值都是要加上c[n]-c[pos]的；
于是我们只需要分析前缀最小值和后缀最小值变化后是否非负即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,ans=0,l,r;
char s[maxn];
int fun(){
int ans=0;
int c[550]={0,},pre[550],sub[550];
rep(i,1,n){
c[i]=c[i-1];
if(s[i]=='(') c[i]++;
else c[i]--;
}
pre[1]=c[1];
rep(i,2,n) pre[i]=min(pre[i-1],c[i]);
sub[n]=c[n];
dep(i,n-1,1) sub[i]=min(sub[i+1],c[i]);
rep(i,0,n-1) if((sub[i+1]-c[i]>=0)&&(pre[i]+c[n]-c[i]>=0)) ans++;
return ans;
}
int main(){
scanf("%d%s",&n,s+1);
int l=0,r=0;
rep(i,1,n){
if(s[i]=='(') l++;
else r++;
}
if(l!=r) return printf("0\n1 1\n"),0;
rep(i,1,n) rep(j,i,n){
char t1=s[i],t2=s[j];
s[i]=t2;s[j]=t1;
int tmp=fun();
if(tmp>ans){
ans=tmp;l=i;r=j;
}
s[i]=t1;s[j]=t2;
}
if(ans==0) printf("0\n1 1\n");
else printf("%d\n%d %d\n",ans,l,r);
}
