看看这里
自己把题目翻译一遍就当,考研翻译训练了()
最后一题,心态爆炸了
A T or T
题意
我们有$N$个人要去旅行,通过乘坐火车或者出租车进行出游,坐火车我们每个人要出$A$元(日元),做出租车我们总共会花费$B$元。请问,我们的旅费最少是多少?
思路
直接计算两种出行方式的总花费,输出最小值
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int n = read(), a = read(), b = read();
cout << min(n * a, b) << endl;
return 0;
}
B Good Distance
题意
在$D$维度空间中有$N$个点,第$i$个点的坐标为 $ \left (x_1, x_2,…,x_n \right ) $,问有多少对点对,两点之间的距离是整数
思路
两重for循环枚举就行
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int n = read(), d = read();
vector<vector<int>> a(n + 1, vector<int>(d + 1));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= d; j++) a[i][j] = read();
int cnt = 0;
for(int i = 1 ; i <= n ; ++i){
for(int j = i + 1 ; j <= n ; ++j){
int sum = 0;
for(int k = 1 ; k <= d ; ++k)
sum = sum + (a[i][k] - a[j][k]) * (a[i][k] - a[j][k]);
if((int)sqrt(sum) * (int)sqrt(sum) == sum) ++cnt;
}
}
cout << cnt << endl;
return 0;
}
C Remainder Minimization 2019
题意
给你两个非负整数$L$和$R$,我们将会选择两个整数$i$ 和 $j$($L \le i < j \le R$),遭到最小的$(i * j) % 2019$
思路
当区间范围超过$2019$时,则区间内必然有2019的倍数,所以必然有$(i * j) % 2019 = 0$
如果区间范围小于$2019$,直接枚举所有状况就行
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int l = read(), r = read();
if(l > r) swap(l, r);
if(r - l + 1 >= 2019) cout << 0;
else {
int mn = 1e18;
for(int i = l; i <= r; i++)
for(int j = i + 1; j <= r; j++)
mn = min(mn, i * j % 2019);
cout << mn << endl;
}
return 0;
}
D Rain Flows into Dams
题意
有$N$座山围成一个圈,按照顺时针分别被称为 Mountain 1, Mountain 2, ......, Mountain N,$N$是奇数
在这些山之间有$N$个 Dams,$Dam_i$ 位于 $Mountain_i$ 和 $Mountain_{i + 1}$ 之间((MountainN+1 就是 Mountain 1).)
当山$*i*(1≤*i*≤*N*)$降雨量为$2*x*$升时,$dam_{*i*−1}$和 $dam_*i*$各积水$*x*$升。
有一天,每座山的降雨量都是非负的。
求每座山的降雨量。我们可以证明,在此问题的约束条件下,解是唯一的。
思路
$$ Dam_1 = \frac{a_1}{2} + \frac{a_2}{2} Dam_2 = \frac{a_2}{2} + \frac{a_3}{2} Dam_3 = \frac{a_1}{2} + \frac{a_2}{2} $$
观察可以发现
$$
Dam_1 -Dam_2 + Dam_3 - Dam_4 + … - Dam_{n - 1} = \frac{a_1}{2} - \frac{a_n}{2}
$$
$$ Dam_n = \frac{a_1}{2}+\frac{a_n}{2} $$
$$ \therefore Dam_1 -Dam_2 + Dam_3 - Dam_4 + … - Dam_{n - 1} + Dam_n = a_1 $$
在计算出$a_1$之后,往后递推就能求解出后面的答案
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
signed main()
{
int n = read();
vector<int> a(n), ans(n);
int sum = 0;
for(int i = 0; i < n; i++)
{
a[i] = read();
if(i & 1) sum -= a[i];
else sum += a[i];
}
ans[0] = sum;
for(int i = 1; i < n; i++)
{
ans[i] = (a[i - 1] - ans[i - 1] / 2) * 2;
}
for(int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
return 0;
}
E Virus Tree 2
题意
给你一棵树,它有$N$个顶点和$N-1$条边。顶点的编号为 $1$ 到 $N$,第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。
您有 $K$ 种颜色的着色材料。对于树中的每个顶点,你将从 $K$ 种颜色中选择一种来给它上色,这样就满足了下面的条件:
- 如果两个不同顶点$x$和$y$之间的距离小于或等于 2,则$x$和$y$有不同的颜色。
这棵树有几种涂色方法?求模数 $1\ 000\ 000\ 007$。
什么是树?树是图的一种。详情请参见维基百科 “树(图论)”
什么是距离?两个顶点$x$和$y$之间的距离是从$x$到$y$所需经过的最少边数。
思路
一开始想树形dp,求$ \sum_{i=1}^{k} dp_{1,i} $ 作为答案,但是根据数据范围发现,内存会爆
然后考虑特殊性质
根节点有$K$种选择,根节点的孩子有$K-1$种选择,其余节点最多有$K-2$种选择
对于一个已经确定颜色的节点来说,他的有$x$个子节点,如果则它的子节点的情况有$\frac{ use!}{(use-x)!} $种
然后遍历子节点,结果乘上子节点确定颜色可能的情况
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
const int mod = 1e9 + 7;
signed main()
{
int n = read(), k = read();
vector<vector<int>> g(n + 1);
for(int i = 1; i < n; i++)
{
int u = read(), v = read();
g[u].emplace_back(v);
g[v].emplace_back(u);
}
function<int(int, int)> dfs = [&](int u, int fa) -> int
{
int use;
if(fa == 0) {
use = k - 1;
} else {
use = k - 2;
}
if(k < g[u].size()) return 0;
int res = 1;
for(auto x : g[u])
{
if(x == fa) continue;
res *= use--;
res %= mod;
}
for(auto x : g[u])
{
if(x == fa) continue;
res *= dfs(x, u);
res %= mod;
}
return res;
};
cout << k * dfs(1, 0) % mod << endl;
return 0;
}
F Colorful Tree
题意
有一棵树,其顶点为 $N$,编号为 $1$至 $N$。这棵树的第$i$条边连接顶点$a_i$和顶点$b_i$,这条边的颜色和长度分别是$c_i$和$d_i$。在这里,每条边的颜色由一个介于 $1$和 $N-1$(含)之间的整数表示。相同的整数对应相同的颜色,不同的整数对应不同的颜色。
请回答下列 $Q$ 个问题:
- 查询题$j$($1 \leq j \leq Q$):假设颜色为$x_j$的每条边的长度都改为$y_j$,求顶点$u_j$与顶点$v_j$之间的距离(边长的改变不影响后面的查询)。
思路
也不算思路了,这题我没写出来,树剖+线段树这点是没问题的,对与边进行树剖,这种题也做过也没问题,计算距离就是考虑LCA,$*d*(*u*)+*d*(*v*)−2×*d*(*L**C**A*(*u*,*v*))$,路径的长度就用线段树维护,但是每次查询的按颜色修改都是暴力修改的,时间复杂度非常糟糕,在写了40min之后不出意料的TLE了,最后投降,看了一下题解是用可持久化数据做的,也有离线处理做优化的,看了半天,好像懂了()
code
这是一份霓虹的代码
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
struct HLDecomposition {
Int n,pos;
vector<vector<Int> > G;
vector<Int> vid, head, sub, par, dep, inv, type;
HLDecomposition(){}
HLDecomposition(Int n):
n(n),pos(0),G(n),vid(n,-1),head(n),sub(n,1),
par(n,-1),dep(n,0),inv(n),type(n){}
void add_edge(Int u, Int v) {
G[u].push_back(v);
G[v].push_back(u);
}
void build(vector<Int> rs={0}) {
Int c=0;
for(Int r:rs){
dfs_sz(r);
head[r]=r;
dfs_hld(r,c++);
}
}
void dfs_sz(Int v) {
for(Int &u:G[v]){
if(u==par[v]) continue;
par[u]=v;
dep[u]=dep[v]+1;
dfs_sz(u);
sub[v]+=sub[u];
if(sub[u]>sub[G[v][0]]) swap(u,G[v][0]);
}
}
void dfs_hld(Int v,Int c) {
vid[v]=pos++;
inv[vid[v]]=v;
type[v]=c;
for(Int u:G[v]){
if(u==par[v]) continue;
head[u]=(u==G[v][0]?head[v]:u);
dfs_hld(u,c);
}
}
// for_each(vertex)
// [l,r] <- attention!!
template<typename F>
void for_each(Int u, Int v, const F& f) {
while(1){
if(vid[u]>vid[v]) swap(u,v);
f(max(vid[head[v]],vid[u]),vid[v]);
if(head[u]!=head[v]) v=par[head[v]];
else break;
}
}
template<typename T,typename Q,typename F>
T for_each(Int u,Int v,T ti,const Q &q,const F &f){
T l=ti,r=ti;
while(1){
if(vid[u]>vid[v]){
swap(u,v);
swap(l,r);
}
l=f(l,q(max(vid[head[v]],vid[u]),vid[v]));
if(head[u]!=head[v]) v=par[head[v]];
else break;
}
return f(l,r);
}
// for_each(edge)
// [l,r] <- attention!!
template<typename F>
void for_each_edge(Int u, Int v,const F& f) {
while(1){
if(vid[u]>vid[v]) swap(u,v);
if(head[u]!=head[v]){
f(vid[head[v]],vid[v]);
v=par[head[v]];
}else{
if(u!=v) f(vid[u]+1,vid[v]);
break;
}
}
}
Int lca(Int u,Int v){
while(1){
if(vid[u]>vid[v]) swap(u,v);
if(head[u]==head[v]) return u;
v=par[head[v]];
}
}
Int distance(Int u,Int v){
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
};
struct FastIO{
FastIO(){
cin.tie(0);
ios::sync_with_stdio(0);
}
}fastio_beet;
template <typename T>
struct SegmentTree{
using F = function<T(T,T)>;
Int n;
F f;
T ti;
vector<T> dat;
SegmentTree(){};
SegmentTree(F f,T ti):f(f),ti(ti){}
void init(Int n_){
n=1;
while(n<n_) n<<=1;
dat.assign(n<<1,ti);
}
void build(const vector<T> &v){
Int n_=v.size();
init(n_);
for(Int i=0;i<n_;i++) dat[n+i]=v[i];
for(Int i=n-1;i;i--)
dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
}
void set_val(Int k,T x){
dat[k+=n]=x;
while(k>>=1)
dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
}
T query(Int a,Int b){
T vl=ti,vr=ti;
for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
if(l&1) vl=f(vl,dat[l++]);
if(r&1) vr=f(dat[--r],vr);
}
return f(vl,vr);
}
template<typename C>
Int find(Int st,C &check,T &acc,Int k,Int l,Int r){
if(l+1==r){
acc=f(acc,dat[k]);
return check(acc)?k-n:-1;
}
Int m=(l+r)>>1;
if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
if(st<=l&&!check(f(acc,dat[k]))){
acc=f(acc,dat[k]);
return -1;
}
Int vl=find(st,check,acc,(k<<1)|0,l,m);
if(~vl) return vl;
return find(st,check,acc,(k<<1)|1,m,r);
}
template<typename C>
Int find(Int st,C &check){
T acc=ti;
return find(st,check,acc,1,0,n);
}
};
//INSERT ABOVE HERE
signed main(){
Int n,q;
cin>>n>>q;
vector<Int> as(n),bs(n),cs(n),ds(n);
vector<Int> xs(q),ys(q),us(q),vs(q);
vector< vector<Int> > C(n),D(n);
HLDecomposition hld(n);
for(Int i=1;i<n;i++){
cin>>as[i]>>bs[i]>>cs[i]>>ds[i];
as[i]--;bs[i]--;
hld.add_edge(as[i],bs[i]);
C[cs[i]].emplace_back(i);
}
hld.build();
for(Int i=0;i<q;i++){
cin>>xs[i]>>ys[i]>>us[i]>>vs[i];
us[i]--;vs[i]--;
D[xs[i]].emplace_back(i);
}
auto f=[&](Int a,Int b){return a+b;};
Int ti=0;
SegmentTree<Int> cnt(f,ti);
SegmentTree<Int> sum(f,ti);
cnt.build(vector<Int>(n,0));
sum.build(vector<Int>(n,0));
for(Int i=1;i<n;i++){
Int ch=hld.dep[as[i]]>hld.dep[bs[i]]?as[i]:bs[i];
sum.set_val(hld.vid[ch],ds[i]);
}
vector<Int> ans(q,0);
for(Int i=0;i<q;i++){
Int res=0;
auto qry=[&](Int l,Int r){res+=sum.query(l,r+1);};
hld.for_each_edge(us[i],vs[i],qry);
ans[i]+=res;
}
sum.build(vector<Int>(n,0));
for(Int t=1;t<n;t++){
for(Int i:C[t]){
Int ch=hld.dep[as[i]]>hld.dep[bs[i]]?as[i]:bs[i];
cnt.set_val(hld.vid[ch],1);
sum.set_val(hld.vid[ch],ds[i]);
}
for(Int i:D[t]){
Int res=0,num=0;
auto qry=[&](Int l,Int r){
num+=cnt.query(l,r+1);
res+=sum.query(l,r+1);
};
hld.for_each_edge(us[i],vs[i],qry);
ans[i]+=num*ys[i];
ans[i]-=res;
}
for(Int i:C[t]){
Int ch=hld.dep[as[i]]>hld.dep[bs[i]]?as[i]:bs[i];
cnt.set_val(hld.vid[ch],0);
sum.set_val(hld.vid[ch],0);
}
}
for(Int i=0;i<q;i++) cout<<ans[i]<<"\n";
cout<<flush;
return 0;
}
nya是什么意思
猫叫