题目面板 提取码：k2fu
A. 胡图图的数学难题
这道题很有意思让你求斐波那契数列的平方和，一篇易懂的题解 得到公式以后直接一个矩阵快速幂就解决了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
struct node{
ll mat[2][2];
void set(){
memset(mat,0,sizeof mat);
for(int i=0;i<2;i++) mat[i][i]=1;
}
node operator * (const node &o){
node ans;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
ll sum=0;
for(int k=0;k<2;k++){
sum=(sum+mat[i][k]*o.mat[k][j]%MOD)%MOD;
}
ans.mat[i][j]=sum;
}
}
return ans;
}
};
node p={
1,1,
1,0
};
node ksm(node x,ll n){
node ans;
ans.set();
while(n){
if(n&1) ans=ans*x;
x=x*x;
n>>=1;
}
return ans;
}
int main()
{
ios;
ll n;
cin>>n;
node unit=ksm(p,n-2);
ll a=(unit.mat[0][0]+unit.mat[0][1])%MOD;
ll b=(unit.mat[1][0]+unit.mat[1][1])%MOD;
ll c=(a+b)%MOD;
cout<<(a*c)%MOD<<'\n';
return 0;
}
|
C. 胡图图公司大整改
这道题是线段树的升级版，朴素版线段树是对一个连续的线段实现单点修改区间查询，而这道题则是在树上实现单点修改，区间查询，1结点是根节点，所以这道题就添加了一个操作把这n个点建成树的样子，然后对它们进行编号，编号方式是优先遍历子树，遍历到谁编号加一，这里用low数组来实现这个功能，到这里单点修改已经可以实现了，已经把一个线段上的每一个点都映射到了树上，但是区间查询还没有办法实现，为什么实现不了？这里要查询的是一个点的子树，这里的子树就相当于区间，我们上面优先遍历子树因此遍历完后，子树上的每一个点的序号是连续的，所以可以用high数组来记录子树区间的右端点，当遍历完一个点的所有子节点时就记录一下当前的序号，那么[lowi,highi]就表示了子树里面的点
总之这道题知识点就是用了一个dfs实现了将线段上的点映射到树上并且给之编号，实现了查询一个点的子树功能
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout );
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll maxn=1e5+10;
const ll inf=0x3f3f3f3f ;
ll N,Q;
ll w[maxn];
vector<ll> ve[maxn];
ll high[maxn],low[maxn],cnt;
struct node{
ll l,r;
ll minn,maxx;
}tr[maxn*4];
void pushup(ll u){
tr[u].minn=min(tr[u<<1].minn,tr[u<<1|1].minn);
tr[u].maxx=max(tr[u<<1].maxx,tr[u<<1|1].maxx);
}
void build(ll u,ll l,ll r){
tr[u]={l,r};
if(l!=r){
ll mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
}
}
void add(ll u,ll x,ll c){
if(tr[u].l==x && x==tr[u].r){
tr[u].minn+=c;
tr[u].maxx+=c;
}else{
ll mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid) add(u<<1,x,c);
else add(u<<1|1,x,c);
pushup(u);
}
}
node query(ll u,ll l,ll r){
if(l<=tr[u].l && tr[u].r<=r) return tr[u];
else{
ll mid=(tr[u].l+tr[u].r)>>1;
if(r<=mid) return query(u<<1,l,r);
else if(l>mid) return query(u<<1|1,l,r);
else{
node ans,L,R;
L=query(u<<1,l,r);
R=query(u<<1|1,l,r);
ans.minn=min(L.minn,R.minn);
ans.maxx=max(L.maxx,R.maxx);
return ans;
}
}
}
void dfs(ll u,ll fa=-1){
low[u]=++cnt;
for(auto v:ve[u]){
if(v==fa) continue;
dfs(v,u);
}
high[u]=cnt;
}
int main(){
ios;
cin>>N>>Q;
for(ll i=1;i<=N;i++) cin>>w[i];
for(ll i=1;i<=N-1;i++){
ll u,v; cin>>u>>v;
ve[u].pb(v);
ve[v].pb(u);
}
dfs(1);
build(1,1,N);
for(ll i=1;i<=N;i++) add(1,low[i],w[i]);
while(Q--){
ll op,x,y;
cin>>op;
if(op==1){
cin>>x>>y;
add(1,low[x],y);
}else{
cin>>x;
node ans=query(1,low[x],high[x]);
cout<< ans.maxx-ans.minn <<'\n';
}
}
return 0;
}
|
E. 胡图图的难题
1) 让最小的带最大的过去，最小的回来 fi = fii1 + ai + a1
2) 让最小的带第二小的过去，最小的回来，最大的两个过去，第二小的回来 fi = fii 2 + ai + a1 + a1 + a2 ∗* 2
综上所述，fi = min(fii 1 + ai + a1, fi2 + ai + a1 + a2 ∗ 2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <bits/stdc ++.h>
using namespace std;
const int mx =100000+47;
long long n,a[mx],f[mx];
int main () {
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+n+1);
f[1]=a[1];
f[2]=a[2];
f[3]=a[3]+a[2]+a[1];
for(int i=4;i<=n;i++)
f[i]= min(f[i -2]+a[i]+a[1]+(a[2]<<1),f[i -1]+a[i]+a[1]);
printf("%lld\n",f[n]);
}
|
F 胡图图找队友
CODE1
维护一个数组存储每一个点和根节点的关系，是否属于一个集合，因此每次只要通过根节点这个媒介联系两个结点的关系
详细题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<cstdio>
#include<iostream>
#include<algorithm>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAXN=1e3+100;
int fa[MAXN],r[MAXN];
void init(int n){
for(int i=0;i<=n;i++){
fa[i]=i;
r[i]=0;
}
}
int find(int x){
if(x==fa[x]) return x;
int tmp=fa[x];
fa[x]=find(fa[x]);
r[x]=(r[x]+r[tmp])%2;
return fa[x];
}
void Union(int a,int b,int c){
int x=find(a), y=find(b);
if(x!=y){
fa[y]=x;
if(c) r[y]=(r[a]+r[b]+1)%2;
else r[y]=(r[a]+r[b])%2;
}
}
int main()
{
int t,n,m;
scanf("%d%d%d",&n,&m,&t);
init(n);
char c;
int x,y;
while(m--){
scanf("%c%d%d",&c,&x,&y);
if(c=='B') Union(x,y,0);
else Union(x,y,1);
}
while(t--){
int a,b;
scanf("%d%d",&a,&b);
if(find(a)==find(b)){
if(r[a]==r[b]) printf("Yes\n");
else printf("No\n");
}
else printf("Not sure\n");
}
return 0;
}
|
CODE2
第二种思路，前n个作为第一个集合，后n个作为第二个集合，具体查看题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<cstdio>
#include<iostream>
#include<algorithm>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAXN=1e3+100;
int fa[MAXN*2];
void init(int n){
for(int i=0;i<=n;i++) fa[i]=i;
}
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void Union(int a,int b){
int x=find(a), y=find(b);
if(x!=y) fa[y]=x;
}
int main()
{
int t,n,m;
scanf("%d%d%d",&n,&m,&t);
init(2*n);
char c;
int x,y;
while(m--){
scanf(" %c%d%d",&c,&x,&y);
if(c=='B'){
Union(x,y);
Union(x+n,y+n);
}
else{
Union(x+n,y);
Union(x,y+n);
}
}
while(t--){
int a,b;
scanf("%d%d",&a,&b);
if(find(a)==find(b)||find(a+n)==find(b+n)) printf("Yes\n");
else if(find(a+n)==find(b)||find(a)==find(b+n)) printf("No\n");
else printf("Not sure\n");
}
return 0;
}
|
H. 胡图图的好兄弟
记忆化搜索
首先不考虑a1为何值，先预处理出当x > 1时的结果，首先定义一个数组dp[N] [2]，dp[i][j]是指x = i并且执行第j步操作时的最终结果。在过程中记录每一个dp[i][j]下一次再次来到i点便可以直接返回dp[i][j]。在这个过程中可能会遇到回到了a1，但是a1是不确定的。不过并没有影响，题目描述算法输出有两种情况，一个是y，一个是ᱟ 1，什么时候出现⧠ 1，当出现循环的时候，比如说在一次程序运行中，已经计算了dp[i] [j]但是后来有来到了dp[i][j]，很明显此时陷入循环了，那么就会输出ࠪ 1，对于再次经过a1有两种情况，一种是i = 1, j = 0，即下一步x = x + a1，因为程序的第一步都是i = 1, j = 0，所以说，到这里陷入循环输出ࠪ 1。另外一种i = 1 j = 1是不会出现的。预处理完后，我们便可以逐个输dp[i][1] + ii 1(i > 1)，ii 1是指初始时经过a1也就是dp*[1][0]的值。
CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int N=2e5+100;
ll dp[N][2];
int arr[N];
bool vis[N][2];
int n;
void dfs(int i,int j){
if(vis[i][j]) return ;
int nx;
vis[i][j]=1;
if(j&1) nx=i-arr[i];
else nx=i+arr[i];
if(nx<=0||nx>n){
dp[i][j]=arr[i];
return;
}
dfs(nx,j^1);
if(dp[nx][j^1]!=-1){
dp[i][j]=arr[i]+dp[nx][j^1];
}
}
int main()
{
ios;
vis[1][1]=1;
memset(dp,-1,sizeof dp);
cin>>n;
for(int i=2;i<=n;i++) cin>>arr[i];
for(int i=2;i<=n;i++) dfs(i,1);
for(int i=2;i<=n;i++){
if(dp[i][1]!=-1) dp[i][1]+=i-1;
}
for(int i=2;i<=n;i++){
cout<<dp[i][1]<<'\n';
}
return 0;
}
|
I. 胡图图吃桃子
完全背包问题，算是比较模板，不过你得想到完全背包%%%
完全背包初始化我还不理解，不懂什么时候必须初始化一些东西，反正我现在的做法就是把能直接看出来答案的数都初始化一下
详细点击我
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int p[1000],dp[120010];
int main()
{
int w;
cin>>w;
for(int i=1;i<=18;i++) p[i]=pow(i,4);
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=18;i++) dp[p[i]]=1;
for(int i=1;p[i]<=w;i++){
for(int j=p[i];j<=w;j++){
dp[j]=min(dp[j],dp[j-p[i]]+1);
}
}
cout<<dp[w]<<'\n';
return 0;
}
|
这道题我刚开始一直以为贪心做就可以了，但事实证明认为可行也只是我的个人感觉，我刚开始的做法就是每次对这个数开四次根号，再减去这个数的四次方，之前已知都没想到哪里错了，举了很多例子都找不出来错误，事实上例子确实不好找，跑了一下706到1里面错误的都很少，比如704=(4^4^)^2^+(2^4^)^12^,也就是14次，但是贪心每次都去最大四次方数就是二十次，错了
wechat
alipay