作业介绍
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e5+5, Mod = 1e9+7; int t,k,a[N],l,r; signed main(){ cin>>t>>k; a[0] = 1; for(int i = 1; i<=1e5; i++){ if(i-k>=0) a[i] = (a[i-1]+a[i-k])%Mod; else a[i] = a[i-1]; } for(int i = 1; i<=1e5; i++) (a[i] += a[i-1])%=Mod; while(t--){ cin>>l>>r; cout<<(a[r]-a[l-1]+Mod)%Mod<<"\n"; } return 0; }

```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 105,Mod=1e9+7;
#define int long long
int n,k,d;
int f[N][2];
signed main(){
	cin>>n>>k>>d;
	f[0][0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=min(i,k);j++){
			if(j<d){
				f[i][0]+=f[i-j][0];
				f[i][0]%=Mod;
			}
			f[i][1]+=f[i-j][1];
			f[i][1]%=Mod;
			if(j>=d){
				f[i][1] += f[i-j][0];
				f[i][1]%=Mod;
			}
		}
	}
	cout<<f[n][1]<<endl;
	return 0;
} 
#include<iostream>
#include<cstring>
using namespace std;

int n,w[4],f[4010];

int main(){
    cin>>n;
    for(int i=1;i<=3;i++)
        cin>>w[i];
    memset(f,-1,sizeof(f));
    f[0]=0;
    for(int i=1;i<=3;i++)
        for(int j=w[i];j<=n;j++){
            if(f[j-w[i]]!=-1)
                f[j]=max(f[j],f[j-w[i]]+1);
        }
    cout<<f[n]<<endl;
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5,Mod=1e9+7;
int n,l,r,f[N][3],a[3];
signed main(){
	cin>>n>>l>>r;
	a[0] = r/3-(l-1)/3;
	a[1] = (r+2)/3-(l+1)/3;
	a[2] = (r+1)/3-(l)/3;
	f[1][0] = a[0];
	f[1][1] = a[1];
	f[1][2] = a[2];
	for(int i=2;i<=n;i++){
		f[i][0]+=(f[i-1][0]*a[0])%Mod;f[i][0]%=Mod;
		f[i][0]+=(f[i-1][1]*a[2])%Mod;f[i][0]%=Mod;
		f[i][0]+=(f[i-1][2]*a[1])%Mod;f[i][0]%=Mod;
		f[i][1]+=(f[i-1][1]*a[0])%Mod;f[i][1]%=Mod;
		f[i][1]+=(f[i-1][2]*a[2])%Mod;f[i][1]%=Mod;
		f[i][1]+=(f[i-1][0]*a[1])%Mod;f[i][1]%=Mod;
		f[i][2]+=(f[i-1][2]*a[0])%Mod;f[i][2]%=Mod;
		f[i][2]+=(f[i-1][0]*a[2])%Mod;f[i][2]%=Mod; 
		f[i][2]+=(f[i-1][1]*a[1])%Mod;f[i][2]%=Mod;
	//	cout<<f[i][0]<<" "<<f[i][1]<<" "<<f[i][2]<<endl;
	}
	cout<<f[n][0]<<endl;
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n,f[N];
int a[N],b[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		b[x] = y;
	}
	int Max = 0;
	for(int i=0;i<=1000000;i++){
		if(b[i]==0) f[i] = f[i-1];
		else if(b[i]>i)f[i] = 1;
		else f[i] = f[i-b[i]-1]+1;
		Max = max(Max,f[i]);
	}
	cout<<n-Max<<endl;
	return 0;
}
/*
f[i][0]第i个boos我击败的花费
f[i][1]第i个boos朋友击败的花费
f[i][0] = min(f[i-1][1],f[i-2][1]);
f[i][1] = min(f[i-1][0]+a[i],f[i-2][0]+a[i]+a[i-1])
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int T, n, a[N], f[N][2];

int main() {
	cin >> T;
	while (T--) {
		memset(f, 0x3f, sizeof(f));
		memset(a, 0, sizeof(a));
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		f[1][1] = a[1];
		f[0][0] = 0;
		for (int i = 2; i <= n; i++) {
			f[i][0] = min(f[i - 1][1], f[i - 2][1]);
			f[i][1] = min(f[i - 1][0] + a[i], f[i - 2][0] + a[i] + a[i - 1]);
		}
		cout << min(f[n][0], f[n][1]) << endl;
	}
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, a[N], cnt = 0;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] == 1)
			cnt++;
		if (a[i] == 0)
			a[i] = 1;
		else
			a[i] = -1;
	}
	int res = -100,ans=-100;
	for (int i = 1; i <= n; i++) {
		res = max(res + a[i], a[i]);
		ans = max(ans,res);
	}
	cout << cnt + ans << endl;
	return 0;
}
/*
0 1 2 3 4 5 6 7 8 9 10

ans+=0 + 2 + 4 + 6 + 8 +10

1-0 3-2 5-4 7-6 9-8
2-1 4-3 6-5 8-7 10-9
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int T, n, a[N], b[N], c[N];
signed main() {
	cin >> T;
	while (T--) {
		cin >> n;
		int res = 0;
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		memset(c, 0, sizeof(c));
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			if (i % 2 == 0) {
				res += a[i];
			}
		}
		int sum1 = 0, res1 = 0;
		for (int i = 0; i < n; i += 2) {
			b[i] = a[i + 1] - a[i];
			res1 = max(res1 + b[i], b[i]);
			sum1 = max(sum1, res1);
		}
		int sum2 = 0, res2 = 0;
		for (int i = 1; i + 1 < n; i += 2) {
			c[i] = a[i] - a[i + 1];
			res2 = max(res2 + c[i], c[i]);
			sum2 = max(sum2, res2);
		}
		//3 1 2 1
		//
		//
		res2 = max(res2 - a[0], -a[0]);
		sum2 = max(sum2, res2);
	//	cout << sum1 << " " << sum2 << endl;
		int Max = max(sum1, sum2);
		cout << res + Max << endl;
	}
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+5;
#define int long long
int n,k,f[N][505],res=0;
vector<int>e[N];
void dfs(int x,int fa){
	f[x][0] = 1;
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs(v,x);
		for(int i=0;i<=k-1;i++){
			res+=f[v][i]*f[x][k-i-1];
		}
		for(int i=1;i<=k;i++){
			f[x][i]+=f[v][i-1];
		}
		
	}
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	cout<<res<<endl;
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,a[N],f[N],g[N];
vector<int>e[N];
void dfs1(int x,int fa){
	f[x] = a[x];
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs1(v,x);
		f[x]+=max(0,f[v]);
	}
}
void dfs2(int x,int fa){
	if(x==1)g[x] = a[x];
	else{
		g[x] = a[x]+max(0,g[fa]+f[fa]-max(0,f[x])-a[fa]);
	}
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs2(v,x);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==0)a[i] = -1;
	}
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++){
		cout<<f[i]+max(0,g[i]-a[i])<<" ";
	}
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5,Mod=1e9+7;
int T,n,m,a[N],siz[N],tot;
vector<int>e[N];
int f[N];
void dfs(int x,int fa){
	siz[x] = 1;
	for(auto v:e[x]){
		if(v==fa)continue;
		dfs(v,x);
		f[++tot] = siz[v]*(n-siz[v]);
		siz[x]+=siz[v];
	}
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)e[i].clear(),siz[i]=0;
		tot = 0;
		for(int i=1;i<n;i++){
			int x,y;
			cin>>x>>y;
			e[x].push_back(y);
			e[y].push_back(x);
		}
		dfs(1,0);
		sort(f+1,f+tot+1,greater<int>());
		cin>>m;
		for(int i=1;i<=m;i++){
			cin>>a[i];
		}
		sort(a+1,a+m+1,greater<int>());
		if(m<=tot){
			for(int i=m+1;i<=tot;i++){
				a[i] = 1;
			}
			int res = 0;
			for(int i=1;i<=tot;i++){
				res+=(a[i]*f[i])%Mod;
				res%=Mod;
			}
			cout<<res<<endl;
		}
		else{
			int res = f[1];
			for(int i=1;i<=m;i++){
				if(i<=m-tot+1){
					res*=a[i];
					res%=Mod;
				}
				else res+=(a[i]*f[i-m+tot])%Mod;
				res%=Mod;
			}
			cout<<res<<endl;
		}
	}
	return 0;
}