A
我们发现满足就是
,所以输出
就行了，注意特判
CODE
#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
#define pb(x) push_back(x)
#define lowbit(x) x & -x
I int read() {
int s = 0 , w = 1; char ch = getchar();
while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
return s * w;
}
int n;
signed main() {
cin >> n;
if(n == 1) {
puts("2") ; return 0;
}
cout << n + n - 1 << endl;
return 0;
} B
我们发现不变
越大时，
越小，
越大。
这里提供一个乱搞的贪心做法：我们将每一个数转化为二进制，每一位拆开，某一位上的数，预处理前缀和，首先枚举
，如果顺序枚举
的话肯定会超时，我们枚举
二进制下是1的那一位上的那个数列上
之后第一个是
的位置
，作为
的位置，不难证明这是正确的。
时间复杂度
CODE
#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
#define pb(x) push_back(x)
#define lowbit(x) x & -x
I int read() {
int s = 0 , w = 1; char ch = getchar();
while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
return s * w;
}
const int N = 1e5 + 5;
int n , a[N] , to[20][N] , sum[N] , s[21][N] , Ans;
I int calc_and(int l , int r) {
int res = 0;
For(i , 0 , 20) {
if(s[i][r] - s[i][l - 1] == r - l + 1) res += pow(2 , i);
}
return res;
}
signed main() {
//freopen("1.in" , "r" , stdin);
n = read();
For(i , 1 , n + 1) {
if(i <= n) a[i] = read() , sum[i] = sum[i - 1] + a[i];
For(j , 0 , 20) {
if( !( (a[i] >> j) & 1 ) && ((a[i - 1] >> j) & 1)) {
for(int k = i - 1 ; k >= 1 ; -- k) {
if(!( (a[k] >> j) & 1 )) break;
to[j][k] = i - 1;
}
}
s[j][i] = s[j][i - 1] + ( (a[i] >> j) & 1 );
}
}
For(i , 1 , n) {
Ans = max(Ans , a[i] * a[i]);
For(j , 0 , 20)
if((a[i] >> j) & 1) {
Ans = max(Ans , (sum[to[j][i]] - sum[i - 1]) * calc_and(i , to[j][i]));
}
}
cout << Ans << endl;
return 0;
}
/*
10
2 3 12 4 212 4 2 1 3 33
*/ D
直接爆搜。
当两个点有直接相连的边时，假设他们在一个团里，那么显然和他们相连的点都要与两个点都直接相连，所以我们就去找到某个点，和两个点中一个相连一个不相连。枚举删边加边即可。
E
这不是原题吗。
二分一个答案，判定的时候贪心地条，判断需要移动的石头是否符合题意
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define R register int
const int N = 5e5 + 5;
inline int read() {
int s = 0 , w = 1; char ch = getchar();
while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) ,ch = getchar();
return s * w;
}
int n , m , ans , a[N];
inline bool judge(int mid) {
R i , j = 0 , cnt = 0;
for(i = 1 ; i <= n ; ++ i)
if(a[i] - a[j] >= mid) j = i , ++ cnt;
if(a[n + 1] - a[j] < mid) -- cnt;
return cnt >= n - m;
}
int main() {
// freopen("stone.in","r",stdin);
// freopen("stone.out","w",stdout);
R i ;
int mid , l = 1 , r = read();
n = read() , m = read();
for(i = 1 ; i <= n ; ++ i) a[i] = read();
a[n + 1] = r;
while(l <= r) {
mid = (l + r) >> 1;
if(judge(mid)) ans = mid , l = mid + 1;
else r = mid - 1;
}
cout << ans << endl;
fclose(stdin); fclose(stdout);
return 0;
}
F
显然树上经过一条边的路径数量是这条边两边的点数之积，计算经过每条边的路径数量然后排序从大到小染色即可。
#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
#define pb(x) push_back(x)
#define lowbit(x) x & -x
I int read() {
int s = 0 , w = 1; char ch = getchar();
while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
return s * w;
}
const int N = 1e6 + 5;
int n , head[N] , tot , f[N] , a[N];
struct Edge {
int to , nxt;
} e[N << 1];
I void addedge(int x , int y) {
e[++ tot] = (Edge) {y , head[x]} , head[x] = tot;
}
I void dfs(int u , int par) {
f[u] = 1;
Next(i , u) {
int v = e[i].to;
if(v == par) continue;
dfs(v , u) ;
f[u] += f[v];
}
if(f[u] && f[u] != n) a[++ tot] = f[u] * (n - f[u]);
}
signed main() {
n = read();
For(i , 1 , n - 1) {
int u = read() , v = read();
addedge(u , v) ; addedge(v , u);
}
tot = 0 ;
dfs(1 , 1);
sort(a + 1 , a + tot + 1 , greater <int> ());
int Ans = 0;
//For(i , 1 , tot) printf("%d \n" , a[i]);
For(i , 1 , tot) Ans += a[i] * i;
cout << Ans << endl;
return 0;
} 
京公网安备 11010502036488号