20200314题解
分类:
IT文章
•
2023-11-17 20:27:54
CCF T1
分析只有当n=1或n=2或n=5时才会买不完,除此之外尽量买一套,剩余情况直接暴力枚举吧
#include <iostream>
#include <cstdio>
#include <cstring>
#define LD long double
using namespace std;
long long read(){
long long ans = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = ((ans << 1) + (ans << 3) + (ch ^ 48)), ch = getchar();
while(ch >= '0' && ch <= '9');
return ans * f;
}
int main(){
int n = read(), a = 0, b = 0, c = 0;
a = b = c = n / 14, n %= 14;
if(n == 1 || n == 2 || n == 5){
if(!a){
printf("-1");
return 0;
}
n += 14, a--, b--, c--;
}
int a2 = -a-1, b2 = -b-1, c2 = -c-1;
for(int i=0; i<=n; i+=7)
for(int j=0; i+j<=n; j+=4)
for(int k=0; i+j+k<=n; k+=3)
if(i + j + k == n && i/7+j/4+k/3 > a2+b2+c2)
a2 = i / 7, b2 = j / 4, c2 = k / 3;
printf("%d %d %d", a+a2, b+b2, c+c2);
return 0;
}
View Code
CCF T2
裸的五边形数定理应用,打出模板就完了
#include <iostream>
#include <cstdio>
#include <cstring>
#define LD long double
using namespace std;
long long read(){
long long ans = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = ((ans << 1) + (ans << 3) + (ch ^ 48)), ch = getchar();
while(ch >= '0' && ch <= '9');
return ans * f;
}
const int MAXN = 100005;
long long f[MAXN], Dp[MAXN];
int main(){
int n = read(), MOD = read();
for(int i=1; f[f[0]] <= n; i++){
f[++f[0]] = i * (3 * i - 1) / 2;
f[++f[0]] = i * (3 * i + 1) / 2;
}
Dp[0] = 1;
for(int i=1; i<=n; i++){
for(int j=1; j<=f[0] && f[j]<=i; j++)
Dp[i] = (Dp[i] + MOD + Dp[i-f[j]] * (((j - 1) % 4 <= 1) ? 1 : -1)) % MOD;
}
printf("%d", Dp[n]);
return 0;
}
View Code
CCF T3
矩阵乘法,第a个矩阵val[i][j]表示从i到j用a次魔法的花费,快速幂即可。第1个矩阵可以通过枚举边O(n^2m)时间复杂度初始化
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long read(){
long long ans = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = ((ans << 1) + (ans << 3) + (ch ^ 48)), ch = getchar();
while(ch >= '0' && ch <= '9');
return ans * f;
}
const int MAXN = 101, MAXM = 2501;
struct Matrix{
int size;
long long value[MAXN][MAXN];
void normal(){
for(int i=1; i<=size; i++)
for(int j=1; j<=size; j++)
value[i][j] = (i == j) ? 0 : 1e15;
}
void operator *= (Matrix &other){
long long ans[MAXN][MAXN];
memset(ans, 127, sizeof(ans));
for(int i=1; i<=size; i++)
for(int j=1; j<=size; j++)
for(int k=1; k<=size; k++)
ans[i][j] = min(ans[i][j], value[i][k] + other.value[k][j]);
for(int i=1; i<=size; i++)
for(int j=1; j<=size; j++)
value[i][j] = ans[i][j];
}
void operator ^= (long long n){
Matrix unit = (*this);
this->normal();
while(n){
if(n & 1) (*this) *= unit;
unit *= unit, n >>= 1;
}
}
}g;
int U[MAXM], V[MAXM], C[MAXM];
long long Dp[MAXN][MAXN];
int main(){
int N = read(), M = read(), K = read();
g.size = N;
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
Dp[i][j] = g.value[i][j] = (i == j) ? 0 : 1e15;
for(int i=1; i<=M; i++){
U[i] = read(), V[i] = read(), C[i] = read();
Dp[U[i]][V[i]] = C[i];
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
Dp[i][j] = min(Dp[i][j], Dp[i][k] + Dp[k][j]);
if(!K){
printf("%lld", Dp[1][N]);
return 0;
}
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
for(int k=1; k<=M; k++)
g.value[i][j] = min(g.value[i][j], Dp[i][U[k]] + Dp[V[k]][j] - C[k]);
g ^= K;
printf("%lld", g.value[1][N]);
return 0;
}
View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int read(){
int ans = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = ((ans << 1) + (ans << 3) + (ch ^ 48)), ch = getchar();
while(ch >= '0' && ch <= '9');
return ans * f;
}
const int MAXN = 100005, LOGN = 17;
struct G{
int head[MAXN], last[MAXN<<1], next[MAXN<<1], lineNum;
void add(int x,int y){
lineNum++, next[lineNum] = head[x], last[lineNum] = y, head[x] = lineNum;
}
}g;
int val[MAXN], dep[MAXN], size[MAXN], son[MAXN], fa[MAXN][LOGN+1], id[MAXN], top[MAXN];
struct BIT{
int val[MAXN];
void add(int pos,int x){
for(int i=pos; i<MAXN; i+=i&(-i))
val[i] += x;
}
int query(int pos){
int ans = 0;
for(int i=pos; i; i-=i&(-i))
ans += val[i];
return ans;
}
inline int query(int l,int r){
return query(r) - query(l - 1);
}
}bit;
void dfs1(int x,int faNum){
dep[x] = dep[faNum] + 1, size[x] = 1, fa[x][0] = faNum;
for(int i=1; i<=LOGN; i++)
fa[x][i] = fa[fa[x][i-1]][i-1];
for(int l=g.head[x]; l; l=g.next[l]){
int y = g.last[l];
if(y == faNum) continue;
dfs1(y, x), size[x] += size[y];
if(size[y] > size[son[x]]) son[x] = y;
}
}
void dfs2(int x,int topNum){
id[x] = ++id[0], top[x] = topNum;
if(son[x]) dfs2(son[x], topNum);
for(int l=g.head[x]; l; l=g.next[l]){
int y = g.last[l];
if(y != fa[x][0] && y != son[x])
dfs2(y, y);
}
}
int sum(int x,int y){
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]) swap(x, y);
ans += bit.query(id[top[x]], id[x]);
x = fa[top[x]][0];
}
if(dep[x] > dep[y]) swap(x, y);
ans += bit.query(id[x], id[y]);
return ans;
}
inline int LCA(int x,int y){
if(dep[x] < dep[y]) swap(x, y);
for(int i=LOGN; i>=0; i--)
if(dep[fa[x][i]] >= dep[y])
x = fa[x][i];
if(x == y) return x;
for(int i=LOGN; i>=0; i--)
if(fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
inline int LCA(int x,int y,int root){
int lx = LCA(x, root), ly = LCA(y, root);
if(lx == ly) return LCA(x, y);
return (dep[lx] > dep[ly]) ? lx : ly;
}
int main(){
int N = read(), Q = read();
for(int i=1; i<N; i++){
int x = read(), y = read();
g.add(x, y), g.add(y, x);
}
for(int i=1; i<=N; i++)
val[i] = read();
dfs1(1, 0);
dfs2(1, 1);
for(int i=1; i<=N; i++)
bit.add(id[i], val[i]);
int root = 1;
for(int i=1; i<=Q; i++){
int op = read(), x = read();
if(op == 1) root = x;
else if(op == 2){
int v = read();
bit.add(id[x], v - val[x]);
val[x] = v;
}else if(op == 3){
if(x == root) printf("%d
", bit.query(1, N));
else if(id[root] <= id[x] && id[x] <= id[root] + size[root] - 1) printf("%d
", bit.query(id[x], id[x] + size[x] - 1));
else if(id[x] <= id[root] && id[root] <= id[x] + size[x] - 1){
int temp = root;
for(int i=LOGN; i>=0; i--)
if(dep[fa[temp][i]] > dep[x])
temp = fa[temp][i];
printf("%d
", bit.query(1, N) - bit.query(id[temp], id[temp] + size[temp] - 1));
}else printf("%d
", bit.query(id[x], id[x] + size[x] - 1));
}else if(op == 4){
int y = read();
int lca = LCA(x, y, root);
printf("%d
", sum(x, lca) + sum(y, lca) - val[lca]);
}
}
return 0;
}