I was at the end of the preview course, but I still couldn't help writing a set of questions
A
Check in. How many digits of the number are 9.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 3e5 + 5;
int n;
void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {
cout << f << " ";
dbg(r...);
}
template<typename Type>inline void read(Type &xx){
Type f = 1;char ch;xx = 0;
for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;
for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';
xx *= f;
}
void read(){}
template<typename T,typename ...R>void read(T &x,R &...r){
read(x);
read(r...);
}
int main(int argc, char** argv) {
int T;read(T);
while(T--){
read(n);
printf("%d\n",(n+1)/10);
}
return 0;
}
B
When you see m < = 1000, you can guess that it is about the algorithm of m^2, so it is obvious to take the module + open bucket count first. The sum of module M is regarded as weight, so it is transformed into multiple knapsack to find whether there is a scheme.
But the trouble is that dp[m][0] cannot be used directly, because it is affected by dp[0][0] = true and must be true; And the number of schemes cannot be calculated directly. Then we can listen during dp transfer.
It's not difficult. A backpack tag is 1900
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 1e3 + 5;
int n,m,c[N];bool dp[N*15][N];
void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {
cout << f << " ";
dbg(r...);
}
template<typename Type>inline void read(Type &xx){
Type f = 1;char ch;xx = 0;
for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;
for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';
xx *= f;
}
void read(){}
template<typename T,typename ...R>void read(T &x,R &...r){
read(x);
read(r...);
}
void pack(int &tot,bool &ans,int v,int w){
if(!v) return;
++tot;
dwn(j,m-1,0){
dp[tot][j] = dp[tot-1][j] || dp[tot-1][(j-w+m)%m];
if(!j) ans |= dp[tot-1][(j-w+m)%m];
}
}
int main(int argc, char** argv) {
read(n,m);
rep(i,1,n){
int x;read(x);c[x%m+1]++;
}
dp[0][0] = true;
int tot = 0;bool ans = false;
rep(i,1,m){
int u = c[i];
for(int j = 0;(1 << j) < u;++j){
pack(tot,ans,1<<j,(1<<j)*(i-1)%m);
u -= (1 << j);
}
pack(tot,ans,u,u*(i-1)%m);
}
puts(ans ? "YES" : "NO");
return 0;
}
C
Check in. Simple classification discussion.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 3e5 + 5;
int n;
void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {
cout << f << " ";
dbg(r...);
}
template<typename Type>inline void read(Type &xx){
Type f = 1;char ch;xx = 0;
for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;
for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';
xx *= f;
}
void read(){}
template<typename T,typename ...R>void read(T &x,R &...r){
read(x);
read(r...);
}
int main(int argc, char** argv) {
int T;read(T);
while(T--){
read(n);int s = 0;
rep(i,1,n){
int x;read(x);s += x;
}
if(s >= n) printf("%d\n",s-n);
else puts("1");
}
return 0;
}
D
Pit to be filled~
E
At first glance, it's very combinatorial mathematics, and it can't dp. The breakthrough is to make some rooms empty. Therefore, the non empty room is equivalent to the number of classical equations. If you haven't heard of it, you can refer to it My introduction.
Enumerating the number of empty rooms i = 0~min(n-1,k), then C(n,i) selects the empty room, C(n-i+i-1,i) represents n-i variables, and the number of schemes with I is multiplied to be the contribution.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 3e5 + 5,mod = 1e9 + 7;
int n,k;LL fac[N],ifac[N];
void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {
cout << f << " ";
dbg(r...);
}
template<typename Type>inline void read(Type &xx){
Type f = 1;char ch;xx = 0;
for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;
for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';
xx *= f;
}
void read(){}
template<typename T,typename ...R>void read(T &x,R &...r){
read(x);
read(r...);
}
LL q_pow(LL a,LL b,LL mod){
LL ret = 1;
for(;b;b >>= 1){
if(b & 1) ret = ret * a % mod;
a = a * a % mod;
}
return ret;
}
void init(int n){
fac[0] = 1;rep(i,1,n) fac[i] = fac[i-1] * i % mod;
ifac[n] = q_pow(fac[n],mod-2,mod);
dwn(i,n-1,0) ifac[i] = (i+1) * ifac[i+1] % mod;
}
LL C(int x,int y){
if(x < y) return 0;
return fac[x] * ifac[y] % mod * ifac[x-y] % mod;
}
int main(int argc, char** argv) {
read(n,k);
init(n);
int ans = 0;
rep(i,0,min(n-1,k))
ans = (ans + C(n,i) * C(n-1,i) % mod) % mod;
printf("%d\n",ans);
return 0;
}
F
Greedy is based on ranking inequality. The greedy process requires a data structure to maintain the currently optional but unselected subscripts, and supports insertion, deletion and minimum weight calculation. This data structure is the priority queue.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 3e5 + 5;
int n,k,a[N];
void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {
cout << f << " ";
dbg(r...);
}
template<typename Type>inline void read(Type &xx){
Type f = 1;char ch;xx = 0;
for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;
for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';
xx *= f;
}
void read(){}
template<typename T,typename ...R>void read(T &x,R &...r){
read(x);
read(r...);
}
int main(int argc, char** argv) {
read(n,k);rep(i,1,n) read(a[i]);
priority_queue<pair<int,int> > q;
rep(i,1,k) q.push({a[i],i});
LL tot = 0;vector<int> ans(n);
rep(i,k+1,k+n){
if(i <= n) q.push({a[i],i});
pair<int,int> u = q.top();q.pop();
tot += 1LL*u.first*(i-u.second);
ans[u.second-1] = i;
}
printf("%lld\n",tot);
re_(i,0,n) cout << ans[i] << " \n"[i == n-1];
return 0;
}
G
The technique of shortest circuit splicing has forgotten QAQ. The violent method is to directly enumerate all edges. If the shortest path from s to t passing through the current edge is shorter than the existing one after the current edge is connected, the current edge is illegal; Otherwise it's legal.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 1e3 + 5;
int n,m,s,t,a[N][N];
void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {
cout << f << " ";
dbg(r...);
}
template<typename Type>inline void read(Type &xx){
Type f = 1;char ch;xx = 0;
for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;
for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';
xx *= f;
}
void read(){}
template<typename T,typename ...R>void read(T &x,R &...r){
read(x);
read(r...);
}
void bfs(int s,vector<int> &dis){
queue<int> q;q.push(s);dis[s] = 0;
while(!q.empty()){
int u = q.front();q.pop();
rep(v,1,n) if(a[u][v] && (!~dis[v])){
dis[v] = dis[u]+1;
q.push(v);
}
}
}
int main(int argc, char** argv) {
read(n,m,s,t);
rep(i,1,m){
int u,v;read(u,v);a[u][v] = a[v][u] = true;
}
vector<int> dis1(n+1,-1),dis2(n+1,-1);
bfs(s,dis1);
bfs(t,dis2);
int ans = 0;
rep(i,1,n) rep(j,i+1,n) if(!a[i][j]){
int d = min(dis1[i]+1+dis2[j],dis1[j]+1+dis2[i]);
ans += (d >= dis1[t]);
}
printf("%d\n",ans);
return 0;
}
H
Pit to be filled~
I
When you see "minimum maximization", try bisection ans first. How greedy? Consider endpoints. The leftmost number less than x must become X. Then the interval we choose must be as right as possible, because the number on the left does not need to be increased.
At this time, we need a data structure to support interval addition and single point value calculation. This is the differential array, which is maintained with a tree array.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define lowbit(x) ((x) & (-(x)))
const int N = 3e5 + 5;
int n,m,w,a[N],C[N];
void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {
cout << f << " ";
dbg(r...);
}
template<typename Type>inline void read(Type &xx){
Type f = 1;char ch;xx = 0;
for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;
for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';
xx *= f;
}
void read(){}
template<typename T,typename ...R>void read(T &x,R &...r){
read(x);
read(r...);
}
void mdy(int x,int v){
for(;x <= n;x += lowbit(x)) C[x] += v;
}
int qry(int x){
int ans = 0;
for(;x;x -= lowbit(x)) ans += C[x];
return ans;
}
bool jdg(int x){
rep(i,1,n) C[i] = 0;
rep(i,1,n) mdy(i,a[i]),mdy(i+1,-a[i]);
int u = 0;
rep(i,1,n){
int v = qry(i);
if(v >= x) continue;
u += x-v;
if(u > m) return false;
mdy(i,x-v);
mdy(i+w,v-x);
}
return true;
}
int main(int argc, char** argv) {
read(n,m,w);
rep(i,1,n) read(a[i]);
int l = *min_element(a+1,a+n+1),r = *max_element(a+1,a+n+1) + m;
while(l < r){
int mid = (l+r+1)>>1;
if(jdg(mid)) l = mid;
else r = mid-1;
}
printf("%d\n",l);
return 0;
}
J
Is this construction problem not difficult? But there are not enough people
First, we need a conclusion of the diameter of the tree: let a point farthest from the root be u, and take u as the root to find a point v farthest from U. Then the (u,v) path is the diameter of one of the trees. So we construct that 1h+1 is a chain, and h+2d+1 is another subtree (another chain) of point 1, and then all the remaining points are placed below point h.
It is worth noting that some special judgments: 2 * h < D has no solution, and d == 1 cannot construct two subtrees.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 3e5 + 5;
int n,d,h;vector<int> G[N];
vector<pair<int,int> > ans;
void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {
cout << f << " ";
dbg(r...);
}
template<typename Type>inline void read(Type &xx){
Type f = 1;char ch;xx = 0;
for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;
for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';
xx *= f;
}
void read(){}
template<typename T,typename ...R>void read(T &x,R &...r){
read(x);
read(r...);
}
void dfs(int u,int ufa){
if(ufa) ans.push_back({ufa,u});
for(int v: G[u]) dfs(v,u);
}
int main(int argc, char** argv) {
read(n,d,h);
if(2*h < d){
puts("-1");return 0;
}
if(d == 1 && n > 2){
puts("-1");return 0;
}
rep(i,1,h) G[i].push_back(i+1);
rep(i,h+1,d) G[i == h+1 ? 1 : i].push_back(i+1);
rep(i,d+2,n) G[h].push_back(i);
dfs(1,0);
re_(i,0,n-1) printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}