三个小时把能写的写完了2333
A： Array's Hash
Vasya has invented a new hash function of an array. It is calculated as follows. While the array has at least two elements, the first two elements, call them a1 and a2, are deleted, and the new element a2−a1 is inserted to the beginning of the array. When the array has only one element, this number is a value of Vasya's hash function of this array.
Vasya has the array a1, a2,..., an. He performs q operations of the following form: "increase all elements in the segment [lj,rj] by vj". After each operation he wants to know the value of Vasya's hash function of this array.
Input
The first line contains an integer n (1≤n≤500000) — the size of the array.
The second line contains n integers ai (−109≤ai≤109) — the elements of the array.
The third line contains an integer q (1≤q≤200000) — the number of operations.
Each of the next q lines contains three integers lj, rj, vj (1≤lj≤rj≤n, −109≤vj≤109) — the parameters of the j-th operation.
Output
Output q lines. In the j-th line output one integer — the value of Vasya's hash function after the j-th operation.
Example
Input
7
4 2 -5 10 4 -2 6
4
2 4 -8
5 7 2
3 3 -1
3 7 3
Output
7
9
8
11
A：题解
队友A的，水题。
树状数组，分奇数位和偶数位来存。
代码如下：
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 5e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'|ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };
ll c[maxn];
ll a[maxn];
ll d1[maxn];
ll c1[maxn];
ll d2[maxn];
ll sum3[maxn];
ll sum4[maxn];
ll sum1[maxn];
ll sum2[maxn];
//这里开始是有区间修改的版本，用d表示前后项差，d的前i项和即是a[i]，这样可以实现对d修改后，区间【L,R】内的元素也得到改变
void add_odd(ll pos, ll y, ll n) //在pos位置+y，对d
{
for(ll i=pos;i<=n;i+=lowbit(i))
sum1[i] += y, sum2[i] += pos*y; //从这个位置开始，包含pos项的sum都改变。 sum1是d[i]的前缀和，sum2是d[i]*i的前缀和，sum1*pos-sum2就是a的前缀和
}
void add_range_odd(ll l, ll r,ll x, ll n)
{
add_odd(l,x,n), add_odd(r+1,-x,n);
}
ll ask_odd(ll p, ll n)
{
ll ans = 0;
for(ll i=p;i>=1;i-=lowbit(i))
ans += ((p+1)*sum1[i] - sum2[i]);
return ans;
}
void add_even(ll pos, ll y, ll n) //在pos位置+y，对d
{
for(ll i=pos;i<=n;i+=lowbit(i))
sum3[i] += y, sum4[i] += pos*y; //从这个位置开始，包含pos项的sum都改变。 sum1是d[i]的前缀和，sum2是d[i]*i的前缀和，sum1*pos-sum2就是a的前缀和
}
void add_range_even(ll l, ll r,ll x, ll n)
{
add_even(l,x,n), add_even(r+1,-x,n);
}
ll ask_even(ll p, ll n)
{
ll ans = 0;
for(ll i=p;i>=1;i-=lowbit(i))
ans += ((p+1)*sum3[i] - sum4[i]);
return ans;
}
ll n,m;
void init()
{
memset(c,0,sizeof(c));
//memset(d,0,sizeof(d));
memset(sum1,0,sizeof(sum1));
memset(sum2,0,sizeof(sum2));
}
int main()
{
n = read();
ll odd = 0, even = 0;
rep(i,1,n)
{
a[i] = read();
if(i&1)
{
d1[++odd] = a[i] - (i-2<=0?0:a[i-2]);
add_odd(odd,d1[odd],n/2 + n%2);
}
else
{
d2[++even] = a[i] - (i-2<=0?0:a[i-2]);
add_even(even,d2[even],n/2);
}
}
m = read();
rep(i,1,m)
{
ll l = read(), r = read(), y = read();
ll L1, L2, R1, R2;
if(l&1) L1 = l/2 + 1, L2 = l/2 + 1;
else L1 = l/2+1, L2 = l/2;
if(r&1) R1 = r/2 + 1, R2 = r/2;
else
R1 = r/2 , R2 = r/2;
if(r-l+1==1)
{
if(l & 1) L2 = R2 = 0;
else L1 = R1 = 0;
}
if(L1&&R1)
add_range_odd(L1,R1,y,odd);
if(L2&&R2)
add_range_even(L2,R2,y,even); //cout<<L1<<' '<<L2<<' '<<R1<<' '<<R2<<' '<<odd<<' '<<even<<' '<<ask_odd(odd,odd)<<' '<<ask_even(even,even)<<endl;
ll ans = 0;
if(n&1)
ans = ask_odd(odd,odd) - ask_even(even,even);
else
ans = ask_even(even,even) - ask_odd(odd,odd);
printf("%lld\n",ans);
}
return 0;
} B - Bonuses on a Line
There are n bonuses on a line: the i-th bonus is located at the point xi. All coordinates of all bonuses are distinct. You are located at the point with the coordinate 0. How many bonuses can you collect in t seconds, if you can pass the distance 1 in one second?
Input
The first line contains two integers n and t (1≤n≤200000,0≤t≤109) — the number of bonuses and the time limit.
The second line contains n integers x1, x2,..., xn (−109≤xi≤109) — the coordinates of the bonuses. They are sorted in increasing order (x1<x2<…<xn).
Output
Output one integer — the maximum number of bonuses that can be collected in t seconds.
Example
Input
5 6
-4 -1 2 3 7
Output
3
Note
To collect 3 bonuses in t=6 seconds, you must first collect the bonus with the coordinate -1, then the bonus with the coordinate 2, and in the end — the bonus with the coordinate 3. It will take you 5 seconds (1 second to collect the bonus with the coordinate -1, and 4 seconds to go from -1 to 3).
It is impossible to come to the bonus with the coordinate 7 in time. And if you first go to the bonus with the coordinate -4, you can collect only two bonuses (-4 and -1).
B：题解
队友A的水题。
二分答案。
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 2e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'|ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };
ll pos[maxn];
ll neg[maxn];
ll pre1[maxn];
ll pre2[maxn];
ll p1 = 0;
ll p2 = 0;
int main()
{
ll n = read(), t = read();
ll flag = 0;
rep(i,1,n)
{
ll x = read();
if(x < 0) neg[++p1] = -x;
else if(x>0) pos[++p2] = x;
else flag = 1;
}
sort(neg+1,neg+1+p1);
pre1[0] = pre2[0] = 0;
rep(i,1,p1) pre1[i] = pre1[i-1] + neg[i];
rep(i,1,p2) pre2[i] = pre2[i-1] + pos[i];
ll ans = 0;
ll cur = 0;
rep(i,1,p1)
{
if(neg[i] > t) break;
cur ++;
}
ans = max(ans, cur) ;
cur = 0;
rep(i,1,p2)
{
if(pos[i] > t) break;
cur++;
}
ans = max(ans,cur);
rep(i,1,p1)
{
ll tmp = neg[i];
ll Left = t - neg[i] * 2;
if(Left < 0 ) break;
ll idx = upper_bound(pos+1,pos+1+p2, Left) - pos;
idx --;
cur = idx + i;
ans = max(cur,ans);
}
rep(i,1,p2)
{
ll tmp = pos[i];
ll Left = t - pos[i]*2;
if(Left < 0) break;
ll idx = upper_bound(neg+1,neg+1+p1,Left) - neg;
idx --;
cur = idx + i;
ans = max(cur,ans); //if(cur==4) cout<<idx<<' '<<i<<' '<<pre1[i]<<endl;
}
cout<<ans + flag<<'\n';
return 0;
} E - Fluctuations of Mana
A mage is going to visit n magical sources in fixed order. It is known that after visiting the i-th source the mana is changed by ai (this number can be positive, negative or zero). If the mage's mana becomes negative, he dies. What minimal amount of mana should the mage have in the beginning of his journey to successfully visit all n sources and stay alive?
Input
The first line contains an integer n (1≤n≤500000) — the number of magical sources.
The second line contains n integers ai (−109≤ai≤109) — the mana change after visiting the i-th source.
Output
Output one integer — the minimal amount of mana the mage should have to successfully complete his journey.
Example
Input
6
3 -4 2 -3 -2 7
Output
4
E：题解
队友A的，水题。
一个for循环，累加和找出其中的最小的值。
这个最小的值的绝对值就是答案。
代码如下：
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 5e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'|ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };
ll a[maxn];
int main()
{
ll n;
cin>>n;
ll cur = 1e12;
ll ans =0;
rep(i,1,n)
{
ll x = read();
ans += x;
cur = min(cur,ans);
}
ll res = max(-cur, 0LL);
cout<<res<<'\n';
return 0;
} F - Moving Target
You are at the shooting range. There are n windows in front of you, placed in a line from left to right (the leftmost window has number 1, and the rightmost window — number n). There is a target behind one of the windows. The exact location of the target is unknown, and there is no way to determine it. When you shoot in one of the windows, you win if you hit the target, and if you don't, the target, if it is not already behind the rightmost window, moves one window right.
You have to create a strategy that allows to hit a target in a minimal number of shots.
Input
The input contains one integer n (1≤n≤1000) — the number of windows.
Output
In the first line output the integer k (1≤k≤n) — the minimal number of shots to hit the target for sure.
In the second line output k integers ai (1≤ai≤n) — the sequence of window numbers to shot at.
Note that, as you immediately win after hitting the target, there exists a deterministic strategy that allows you to win in a minimal number of shots.
If there are several possible answers, output any of them.
Examples
Input
2
Output
2
1 2
Input
3
Output
2
1 3
F：题解
刚开始因为题目表述有些不清楚，所以想的地方想多了。
因为每次我们打靶，假设我们打1，那么靶子肯定在>=3以后，所以按奇数位打靶一定是最优的。
假若n为奇数，打靶个数为n/2+1，那么打靶子的顺序为，1,3,5...,n;
假若n为偶数, 打靶个数为n/2+1,那么打靶顺序为，1，3，5，....,n-1,n；
代码如下
：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
ll read()
{
ll sign=1,ans=0;
char ch;
ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
sign=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
ans=(ans<<1)+(ans<<3)+(ch^48);
ch=getchar();
}
return sign*ans;
}
int main()
{
int n;
cin>>n;
if(n&1)
{
cout<<n/2+1<<'\n';
for(int i=1; i<=n; i+=2)
cout<<i<<" ";
}
else
{
cout<<n/2+1<<'\n';
for(int i=1; i<=n; i+=2)
cout<<i<<" ";
cout<<n<<'\n';
}
return 0;
} H - Tree Painting
You are given a tree with n vertices and (n−1) edges. At the beginning its edges and vertices are not painted. You can perform the following operation: choose two vertices in the tree and paint the path between them (all vertices and edges along this path are painted).
What is the minimal number of such operations to paint the whole tree (all edges and all vertices)?
Input
The first line contains the integer n (2≤n≤200000) — the number of vertices in the tree.
Each of the next (n−1) lines contains two integers ui, vi (1≤ui,vi≤n,ui≠vi) — the vertices connected by the i-th edge.
Output
Output one integer — the minimal number of operations to paint the tree.
Examples
Input
5
1 2
1 3
1 4
1 5
Output
2
Input
5
1 2
2 3
3 4
4 5
Output
1
Input
4
1 2
3 2
4 2
Output
2
H：题解
队友A的，水题，我第一次wa是因为不小心漏了等于号，i从0开始了。
队友做法：dfs序+线段树。
我的做法：统计入读为1的点的个数，假如n为奇数ans+=1，最后的答案为ans/=2;
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
using namespace std;
#define ll long long
ll read()
{
char ch=getchar();
ll ans=0,sign=1;
while(ch<'0'||ch>'9')
{
if(ch=='-')
sign=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
ans=(ans<<1)+(ans<<3)+(ch^48);
ch=getchar();
}
return ans*sign;
}
int in[200005];
int main()
{
int n;
cin>>n;
int ans=0;
for(int i=0;i<n-1;i++)
{
int x,y;
cin>>x>>y;
in[x]++;
in[y]++;
}
for(int i=1;i<=n;i++)
if(in[i]==1)
ans++;
if(ans&1)
ans+=1;
cout<<ans/2<<'\n';
return 0;
} I - Sorting Colored Array
You are given the array of n integers. Each number in the array is colored. In one operation you can swap two adjacent differently colored elements. Is it possible to sort the array with some number of such operations?
Input
The first line contains the integer n (1≤n≤200000) — the size of the array.
Each of the next n lines contains two integers ai, ci (−109≤ai≤109,1≤ci≤200000) — the value of the i-th element of the array and its color.
Output
Output "YES" or "NO", depending on is it possible to sort the array using the given operation or not.
Examples
Input
6
1 2
-1 3
-3 1
3 2
0 1
2 3
Output
YES
Input
6
1 2
-1 1
-3 1
3 2
0 3
2 3
Output
NO
Note
In the first test the following sequence of operations sorts the array:
1) swap (1, 2) and (-1, 3)
2) swap (1, 2) and (-3, 1)
3) swap (-1, 3) and (-3, 1)
4) swap (3, 2) and (0, 1)
5) swap (1, 2) and (0, 1)
6) swap (3, 2) and (2, 3)
The resulting array will be:
-3 1
-1 3
0 1
1 2
2 3
3 2
In the second test the elements (-1, 1) and (-3, 1) must be swapped to sort the array, but such swap is prohibited.
I:题解
题目表意有些不清楚呀，刚开始以为只要能够成功排序，无论从大到小还是从小到大都行，结果队友wa了50多的那组数据（只考虑的单调递增的），我wa了在第九组数据（考虑了从大到小和从小到大）。所以由此得出，该题的要求的是是否可以按限制条件从小到大排序。
这题的做法就是找出同样颜色的数字，从左到右，是否是升序的，若不是则不能排序成功，若是，则能排序成功。
代码如下：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
using namespace std;
#define ll long long
ll read()
{
char ch=getchar();
ll ans=0,sign=1;
while(ch<'0'||ch>'9')
{
if(ch=='-')
sign=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
ans=(ans<<1)+(ans<<3)+(ch^48);
ch=getchar();
}
return ans*sign;
}
typedef struct
{
ll num;
int cor;
} NODE;
NODE a[200005];
bool cmp(NODE x,NODE y)
{
return x.cor<y.cor;
}
int main()
{
int n;
n=read();
for(int i=0; i<n; i++)
{
a[i].num=read();
a[i].cor=read();
}
stable_sort(a,a+n,cmp);
int flag=0;
bool is=0;
bool in=0,de=0;
int tag=a[0].cor;
for(int i=1; i<n; i++)
{
if(a[i].cor==tag)
{
if(a[i-1].num>a[i].num)
de=1;
else if(a[i-1].num<a[i].num)
in=1;
}
else
{
tag=a[i].cor;
}
}
if(in&&!de||!in&&!de)
cout<<"YES"<<'\n';
else
cout<<"NO"<<'\n';
return 0;
} J - The Battle of Mages
Two mages play the game. Both of them has their own set of creatures. Each creature is characterized by the integer — its strength. At the beginning of the game each mage summons k distinct random creatures from their set of creatures, and each subset of k creatures can be summoned equally likely. The mage who has the greater sum of strengths of their creatures wins. If the sums of strength are equal, the process repeats. If every subset of creatures of both mages always has the same strength, the draw is declared.
It has turned out, that if k=1 or k=3, the first mage has strictly greater chances to win, and if k=2, the second mage has. You have to give an example of sets of creatures of the first and the second mages.
Input
This problem has only one test, and it is empty.
Output
In the first line output one integer n1 (3≤n1≤10) — the number of creatures in the first mage's set.
In the second line output n1 integers s1i (1≤s1i≤10) — the strengths of creatures of the first mage.
In the third line output one integer n2 (3≤n2≤10) — the number of creatures in the second mage's set.
In the fourth line output n2 integers s2i (1≤s2i≤10) — the strengths of creatures of the second mage.
If there are several possible answers, output any of them. It is guaranteed that the solution in the given constraints exists.
Example
Input
Output
3
1 2 3
3
2 2 2
Note
The output example is not an answer for the problem and is given only for better understanding of output format and to clarify the problem statement.
The first mage has three creatures, their strengths are 1, 2 and 3. The second mage has three creatures, all their strengths are equal to 2.
If k=1, the second mage always has fixed strength 2. If the first mage summons the creature with the strength 2, the process repeats. If he summons the creature with the strength 3, he wins, and with the strength 1 — loses. The probability of the first mage to win is 0.5, but the problem requires the first mage to have strictly better chances.
If k=2, the second mage always has strength 4. The first mage can summon the following subsets of creatures: (1, 2), (1, 3), (2, 3). If it is (1, 2), the first mage loses (as 3 < 4), if it is (1, 3) — the game starts again (as 4 = 4), and if it's (2, 3) — he wins. The resulting probability is again 0.5, but the second mage should have better chances in this case.
If k=3, the subsets of the first and second mages are always (1, 2, 3) and (2, 2, 2). They have equal strengths, and we got infinite game restarts. According to the rules, the draw is declared in this case, so the probability of the first mage winning is not greater again.
J：题解
我们只考虑两个魔法师都只有三种牌的情况。
要使得k=1,or,k=3时第一个魔法师获胜，那么第一个魔法师的三张牌中至少有两张牌是大于第二个魔法师的，并且第一个魔法师牌的总和也是大于第二个魔法师的。
要使得k=2时第二个魔法师获胜，那么我们只需要只有两张牌的时候，第二个魔法师赢得次数比第一个魔法师多即可。
那么我们可以得出等式
a1+a2+a3>b1+b2+b2;
要使得上述全部情况成立，需有a1>bn,a2>bn
我们只讨论一种可以赢得情况，剩下得自己想
假设a1>=a2>=a3,b1>=b2>=b3
b3+b2>a2+a3,
b3+b2>=a1+3
b1+b2>a1+a3
b1+b2>a2+a3;
符合上述情况得就是一种答案。
通过比较我们可以得出,
10 8 2
7 6 6
符合答案的情况
代码如下
：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
ll read()
{
ll sign=1,ans=0;
char ch;
ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
sign=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
ans=(ans<<1)+(ans<<3)+(ch^48);
ch=getchar();
}
return sign*ans;
}
int main()
{
cout<<3<<'\n';
cout<<2<<" "<<8<<" 10"<<'\n';
cout<<3<<'\n';
cout<<"7 6 6"<<'\n';
return 0;
} K - Table
There are 4 bars, possibly, having different lengths. Can they be used as the legs of the table, such that:
The legs stay vertically in the vertices of some rectangle;
The surface of the table, possibly, sloping, touches all four legs?
Input
The input contains 4 integers a1, a2, a3, a4 (1≤ai≤109) — the lengths of the bars.
Output
Output "YES" or "NO", depending on it is possible to make a table with the given design or not.
Examples
Input
1 1 1 1
Output
YES
Input
1 5 1 5
Output
YES
Input
1 3 2 2
Output
YES
Input
9 5 11 8
Output
NO
K：题解
我们可以假设一个情境，假如4个支撑的棍子都是4m的，此时的桌面一定是平衡的，假设其中一个棍子少了1m，为了要形成桌子，那么和它对角线的那根棍子一定会下降1m。所以我们可以得出结论，如果有四根棍子，从小到大是a,b,c,d;
如果a+d==b+c的话，是可以形成桌子的。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
using namespace std;
#define ll long long
ll read()
{
char ch=getchar();
ll ans=0,sign=1;
while(ch<'0'||ch>'9')
{
if(ch=='-')
sign=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
ans=(ans<<1)+(ans<<3)+(ch^48);
ch=getchar();
}
return ans*sign;
}
int main()
{
ll a[5];
cin>>a[0]>>a[1]>>a[2]>>a[3];
sort(a,a+4);
if(a[0]+a[3]==a[1]+a[2])
{
cout<<"YES"<<'\n';
}
else
cout<<"NO"<<'\n';
return 0;
} L - The Dragon Land
A hero is going to make a journey through the dragon land. The dragon land is a road, and n dragon lairs are situated along this road. The hero will follow this road, never turning back.
Passing by the dragon lair, it is possible to fight the dragon, kill him and get ai gold. But it is not always profitable to kill all the dragons, as the weapons and armor wear out: after the first battle the hero will have to spend 1 gold on repairing them, after the second battle — 2 gold, and so on, after the k-th battle he will have to spend k gold.
Initially the hero has no gold. At any moment of his journey and after it the hero can't have negative amount of gold.
How much gold the hero can earn in the journey?
Input
The first line contains the integer n (1≤n≤200000) — the number of dragon lairs.
The second line contains n integers ai (1≤ai≤109) — amounts of gold the hero can earn fighting the i-th dragon.
Output
Output one integer — the maximal hero's profit.
Examples
Input
5
8 2 4 9 1
Output
15
Input
2
1 1
Output
0
L：题解
老贪心了，对能赚的钱从大到小排序，直到当前修复装备所需花费>打龙所赚的钱时就离开。
代码如下：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
using namespace std;
#define ll long long
ll read()
{
char ch=getchar();
ll ans=0,sign=1;
while(ch<'0'||ch>'9')
{
if(ch=='-')
sign=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
ans=(ans<<1)+(ans<<3)+(ch^48);
ch=getchar();
}
return ans*sign;
}
bool cmp(ll x,ll y)
{
return x>y;
}
int main()
{
int n;
cin>>n;
ll a[200005];
ll ans=0;
for(int i=0; i<n; i++)
a[i]=read();
sort(a,a+n,cmp);
for(int i=0; i<n; i++)
{
if(ans+a[i]<i+1||i+1>=a[i])
break;
ans+=a[i];
ans-=(i+1);
}
cout<<ans<<'\n';
return 0;
} M - Notifications
Vasya is sitting at a computer. Sometimes he receives notifications about new videos on his favourite Youtube channel. Then,
if he isn't watching any video at the moment, he clicks the notification and starts to watch this video till the end,
if he is already watching a video at the moment, he will firstly watch all unfinished videos (about which he received notification earlier), and then click the new notification and watch the new video till the end.
You are given n parameters of the notifications: the i-th notification is received at the moment of time ti and contains the video of length di. Find when Vasya will stop watching the last video.
Input
The first line contains the integer n (1≤n≤200000) — the number of notifications.
Each of the next n lines contains two integers ti and di (1≤ti,di≤109) — the moment of time when Vasya receives the i-th notification, and the length of the video in this notification.
All ti form non-decreasing sequence, i. e. ti≤ti+1 for all i from 1 to (n−1).
Output
Output one integer — the moment of time when Vasya will stop watching the last video.
Example
Input
5
1 4
3 3
6 1
10 2
10 3
Output
15
Note
In the given example the sequence of Vasya's actions is the following:
1) At the moment 1 he receives a notification about the video of length 4. As he isn't watching any video at the moment, he starts to watch it till the moment of time 5.
2) At the moment 3 he receives a notification about the video of length 3, but he is watching the first video at the moment, so he will start watching this video at the moment 5 (just after the first one) and finish at the moment 8.
3) At the moment 6 he receives a notification about the video of length 1. He will watch it from the moment 8 to the moment 9.
4) From the moment 9 to the moment 10, Vasya is not doing anything.
5) At the moment 10 he receives two notification — about the videos of lengths 2 and 3. He will watch them in the order he receives them, so he will watch the first of them from 10 to 12, and the other one — from 12 to 15.
M：题解
小模拟题。
代码如下：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
using namespace std;
#define ll long long
ll read()
{
char ch=getchar();
ll ans=0,sign=1;
while(ch<'0'||ch>'9')
{
if(ch=='-')
sign=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
ans=(ans<<1)+(ans<<3)+(ch^48);
ch=getchar();
}
return ans*sign;
}
bool cmp(ll x,ll y)
{
return x>y;
}
ll a[200005],b[200005];
int main()
{
int n;
cin>>n;
ll ans=0;
ll t=0;
for(int i=0; i<n; i++)
a[i]=read(),b[i]=read();
for(int i=0;i<n;i++)
{
if(t<a[i])
{
t=a[i];
t+=b[i];
}
else
{
t+=b[i];
}
}
cout<<t<<'\n';
return 0;
} 
京公网安备 11010502036488号