问你一个正n边形，您能否旋转它，让他的某一条边平行于x轴另一条边平行于y轴。
要让他有平行于x轴的边的同时，也有平行于y轴的边。
那么我们只需要让他n边形的360/n是90度的倍数关系即可。画图验证更快。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl ‘\n‘
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<" : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;
//#define int long long
#define lson rt<<1
#define rson rt<<1|1
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> PII;
const int maxn = 1e6 + 10;
void solve(){
ll n;cin>>n;
if (n % 4 == 0) cout << "YES\n";
else
cout << "NO\n";
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
给你一个01串，如果两个字符左边的=1，右边的=0。那么我们可以选择一个消除，让你找到消除到不能消除为止，如果消除后长度相同，那么输出字典序小的。
我们只需要判断在左边的0和右边的1这样的01是消除不了的。在中间的01串只要有1在0的左边，也就是0的数量和1的数量均不为0。这样问题就得到了解决。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl ‘\n‘
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<" : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;
//#define int long long
#define lson rt<<1
#define rson rt<<1|1
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> PII;
const int maxn = 1e6 + 10;
char str[maxn];
void solve(){
int len;
scanf("%d", &len);
getchar();
scanf("%s", str);
int cnt1 = 0, cnt2 = 0;
int i = 0;
while (str[i] == ‘0‘ && i < len) ++i;
int j = len - 1;
while (str[j] == ‘1‘ && j >= 0) --j;
for (int k = i; k <= j; ++k) {
if (str[k] == ‘0‘) ++cnt1;
else
++cnt2;
}
int ans = cnt1 + cnt2;
for (int k = 0; k < i; ++k) cout << 0;
if (cnt1!=0&&cnt2!=0) cout << 0;
for (int k = j + 1; k < len; ++k) cout << 1;
cout << endl;
}
int main(){
int t;
scanf("%d", &t);
// cin>>t;
while(t--){
solve();
}
return 0;
}
给你一些n个价值，有k个朋友。然后n个价值分别为\(a_1,a_2,…a_n\)，然后输入k个数，代表的是分配给朋友的价值的个数。让你求所有分给朋友的数的\(max(\sum (min_k+max_k))\)。
首先我们知道的是如果给第k个朋友只能分1个价值，那么这个朋友的\(max+min\)就是\(x*2\)。
然后我们去考虑整体。为了让所求和最大，显然我们要让小的价值出现的尽量的少，那么我们就先选每个朋友除了最大的价值的剩下能选择的个数(\(w_k-1\))。在选择这些的时候我们从左边开始双指针，跳范围，这样每选一个小的数就跳过去(\(w_k-1)\)个，然后继续选以此类推。
选择打的数的时候我们从右边开始选择，然后选择的时候也是有条件的，我们先给w小的选。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl ‘\n‘
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<" : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;
//#define int long long
#define lson rt<<1
#define rson rt<<1|1
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> PII;
const int maxn = 1e6 + 10;
int a[maxn], w[maxn];
void solve(){
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= k; ++i) cin >> w[i];
sort(a + 1, a + 1 + n);
ll ans = 0;
sort(w + 1, w + 1 + k, greater<int>());
int l = 1, r = n;
for (int i = 1; i <= k;++i){
if (w[i] == 1) break;
ans += a[l];
l += (w[i]-1);
}
for (int i = k; i >= 1;--i){
if(w[i]==1){
ans += 2 * a[r];
}else
ans += a[r];
--r;
}
cout << ans << endl;
}
int main(){
int t;
// scanf("%d", &t);
cin>>t;
while(t--){
solve();
}
return 0;
}
我解释不了。
递推，找规律。
像如这样的题我们是先考虑找规律来试试的，因为毫无头绪。
然后我们在纸上仔细的画图演算选择。
每过两次第三次就可以选择一次根节点的clwa。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl ‘\n‘
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<" : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;
//#define int long long
#define lson rt<<1
#define rson rt<<1|1
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> PII;
const int maxn = 2e6 + 10;
const int mod = 1e9 + 7;
int dp[maxn];
bool vis[maxn];
int main(){
vis[1] = vis[2] = 0;
dp[1] = dp[2] = 0;
for (int i = 3; i < maxn;++i){
dp[i] = (2ll * dp[i - 2] + dp[i - 1]) % mod;
if (!vis[i - 2] && !vis[i - 1]) dp[i] += 1, vis[i] = 1;
else
vis[i] = 0;
}
int t;cin>>t;
while(t--){
int n;cin>>n;
cout << (4ll * dp[n] % mod) << endl;
}
return 0;
}
题给出n个不同类型的食物，m个朋友。让你给朋友定一个来的顺序，以满足以下条件：
动态贪心。
我们从后往前选，如果\(num[x]/num[y]\leq w[i]\)，那么我就把吃这种食物的安排到最后面。
因为他吃的这种食物一定存在。那么我们让他最后吃，然后将另一种食物省下来给其他人吃。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl ‘\n‘
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<" : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;
//#define int long long
#define lson rt<<1
#define rson rt<<1|1
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> PII;
const int maxn = 1e6 + 10;
int w[maxn],num[maxn];
bool vis[maxn];
pair<int, int> a[maxn];
void solve(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> w[i];
vector<vector<int> > edge(n + 10);
for (int i = 1; i <= m;++i){
int x, y;
cin >> x >> y;
++num[x];
++num[y];
a[i] = {x, y};
edge[x].push_back(i);
edge[y].push_back(i);
}
vector<int> ans;
queue<int> q;
for (int i = 1; i <= n;++i)
if (num[i] <= w[i]) q.push(i);
while(!q.empty()){
int now = q.front();
q.pop();
for(auto x:edge[now]){
if (vis[x]) continue;
vis[x] = 1;
ans.push_back(x);
int v = a[x].first;
if (v == now) v = a[x].second;
if (--num[v] == w[v]) q.push(v);
}
}
if(ans.size()==m){
cout << "ALIVE\n";
reverse(ans.begin(), ans.end());
for (auto x : ans) cout << x << " ";
}else
cout << "DEAD\n";
}
int main(){
int t;
// scanf("%d", &t);
// cin>>t;
// while(t--){
// solve();
// }
solve();
return 0;
}
A. FashionabLee
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Lee is going to fashionably decorate his house for a party, using some regular convex polygons...
Lee thinks a regular n-sided (convex) polygon is beautiful if and only if he can rotate it in such a way that at least one of its edges is parallel to the OX-axis and at least one of its edges is parallel to the OY-axis at the same time.
Recall that a regular n-sided polygon is a convex polygon with n vertices such that all the edges and angles are equal.
Now he is shopping: the market has t regular polygons. For each of them print YES if it is beautiful and NO otherwise.
Input
The first line contains a single integer t (1≤t≤104) — the number of polygons in the market.
Each of the next t lines contains a single integer ni (3≤ni≤109): it means that the i-th polygon is a regular ni-sided polygon.
Output
For each polygon, print YES if it‘s beautiful or NO otherwise (case insensitive).
B. AccurateLee
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Lee was cleaning his house for the party when he found a messy string under the carpets. Now he‘d like to make it clean accurately and in a stylish way...
The string s he found is a binary string of length n (i. e. string consists only of 0-s and 1-s).
In one move he can choose two consecutive characters si and si+1, and if si is 1 and si+1 is 0, he can erase exactly one of them (he can choose which one to erase but he can‘t erase both characters simultaneously). The string shrinks after erasing.
Lee can make an arbitrary number of moves (possibly zero) and he‘d like to make the string s as clean as possible. He thinks for two different strings x and y, the shorter string is cleaner, and if they are the same length, then the lexicographically smaller string is cleaner.
Now you should answer t test cases: for the i-th test case, print the cleanest possible string that Lee can get by doing some number of moves.
Small reminder: if we have two strings x and y of the same length then x is lexicographically smaller than y if there is a position i such that x1=y1, x2=y2,..., xi?1=yi?1 and xi<yi.
Input
The first line contains the integer t (1≤t≤104) — the number of test cases.
Next 2t lines contain test cases — one per two lines.
The first line of each test case contains the integer n (1≤n≤105) — the length of the string s.
The second line contains the binary string s. The string s is a string of length n which consists only of zeroes and ones.
It‘s guaranteed that sum of n over test cases doesn‘t exceed 105.
Output
Print t answers — one per test case.
The answer to the i-th test case is the cleanest string Lee can get after doing some number of moves (possibly zero).
C. RationalLee
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Lee just became Master in Codeforces, and so, he went out to buy some gifts for his friends. He bought n integers, now it‘s time to distribute them between his friends rationally...
Lee has n integers a1,a2,…,an in his backpack and he has k friends. Lee would like to distribute all integers in his backpack between his friends, such that the i-th friend will get exactly wi integers and each integer will be handed over to exactly one friend.
Let‘s define the happiness of a friend as the sum of the maximum and the minimum integer he‘ll get.
Lee would like to make his friends as happy as possible, in other words, he‘d like to maximize the sum of friends‘ happiness. Now he asks you to calculate the maximum sum of friends‘ happiness.
Input
The first line contains one integer t (1≤t≤104) — the number of test cases.
Next 3t lines contain test cases — one per three lines.
The first line of each test case contains two integers n and k (1≤n≤2?105; 1≤k≤n) — the number of integers Lee has and the number of Lee‘s friends.
The second line of each test case contains n integers a1,a2,…,an (?109≤ai≤109) — the integers Lee has.
The third line contains k integers w1,w2,…,wk (1≤wi≤n; w1+w2+…+wk=n) — the number of integers Lee wants to give to each friend.
It‘s guaranteed that the sum of n over test cases is less than or equal to 2?105.
Output
For each test case, print a single integer — the maximum sum of happiness Lee can achieve.
D. TediousLee
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Lee tried so hard to make a good div.2 D problem to balance his recent contest, but it still doesn‘t feel good at all. Lee invented it so tediously slow that he managed to develop a phobia about div.2 D problem setting instead. And now he is hiding behind the bushes...
Let‘s define a Rooted Dead Bush (RDB) of level n as a rooted tree constructed as described below.
A rooted dead bush of level 1 is a single vertex. To construct an RDB of level i we, at first, construct an RDB of level i?1, then for each vertex u:
if u has no children then we will add a single child to it;
if u has one child then we will add two children to it;
if u has more than one child, then we will skip it.
Rooted Dead Bushes of level 1, 2 and 3.
Let‘s define a claw as a rooted tree with four vertices: one root vertex (called also as center) with three children. It looks like a claw:
The center of the claw is the vertex with label 1.
Lee has a Rooted Dead Bush of level n. Initially, all vertices of his RDB are green.
In one move, he can choose a claw in his RDB, if all vertices in the claw are green and all vertices of the claw are children of its center, then he colors the claw‘s vertices in yellow.
He‘d like to know the maximum number of yellow vertices he can achieve. Since the answer might be very large, print it modulo 109+7.
Input
The first line contains one integer t (1≤t≤104) — the number of test cases.
Next t lines contain test cases — one per line.
The first line of each test case contains one integer n (1≤n≤2?106) — the level of Lee‘s RDB.
Output
For each test case, print a single integer — the maximum number of yellow vertices Lee can make modulo 109+7.
E. DeadLee
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Lee bought some food for dinner time, but Lee‘s friends eat dinner in a deadly way. Lee is so scared, he doesn‘t want to die, at least not before seeing Online IOI 2020...
There are n different types of food and m Lee‘s best friends. Lee has wi plates of the i-th type of food and each friend has two different favorite types of food: the i-th friend‘s favorite types of food are xi and yi (xi≠yi).
Lee will start calling his friends one by one. Whoever is called will go to the kitchen and will try to eat one plate of each of his favorite food types. Each of the friends will go to the kitchen exactly once.
The only problem is the following: if a friend will eat at least one plate of food (in total) then he will be harmless. But if there is nothing left for him to eat (neither xi nor yi), he will eat Lee instead ×_×.
Lee can choose the order of friends to call, so he‘d like to determine if he can survive dinner or not. Also, he‘d like to know the order itself.
Input
The first line contains two integers n and m (2≤n≤105; 1≤m≤2?105) — the number of different food types and the number of Lee‘s friends.
The second line contains n integers w1,w2,…,wn (0≤wi≤106) — the number of plates of each food type.
The i-th line of the next m lines contains two integers xi and yi (1≤xi,yi≤n; xi≠yi) — the favorite types of food of the i-th friend.
Output
If Lee can survive the dinner then print ALIVE (case insensitive), otherwise print DEAD (case insensitive).
Also, if he can survive the dinner, print the order Lee should call friends. If there are multiple valid orders, print any of them.
Codeforces Round #652 (Div. 2)
原文：https://www.cnblogs.com/waryan/p/13401542.html