喵哈哈村与哗啦啦村的大战（一）
最大值就是全部+3，最小值就是全部-3，注意不能降为负数。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int a[maxn],n;
int main(){
while(cin>>n){
int ans1=0,ans2=0;
for(int i=0;i<n;i++){
cin>>a[i];
ans1+=a[i]+3;
ans2+=max(0,a[i]-3);
}
cout<<ans1<<" "<<ans2<<endl;
}
}
喵哈哈村与哗啦啦村的大战（二）
最优答案就是摆成等边三角形，所有点均分过去，使得每个点都在无限靠近三角形的顶点位置。
那么最少摧毁(n+2)/3个点了。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n;
while(cin>>n){
cout<<(n+2LL)/3LL<<endl;
}
}
喵哈哈村与哗啦啦村的大战（三）
考虑贪心，我们统计所有的和之后，我们每次选择ci最小的，即花费最小的进行操作。
然后不停使得和向着s靠拢，如果最后能靠拢的话，就输出答案，否则就输出impossible。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+6;
const int inf = 1e9+7;
int dp[maxn],a[maxn],c[maxn],l[maxn],r[maxn];
vector<pair<int,int> > sp[2];
int main(){
int n,s;
while(scanf("%d%d",&n,&s)!=EOF){
sp[0].clear();
sp[1].clear();
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&a[i],&c[i],&l[i],&r[i]);
}
int sum1=0,sum2=0,sum3=0;
for(int i=1;i<=n;i++){
sum1+=l[i];
sum2+=a[i];
sum3+=r[i];
sp[0].push_back(make_pair(c[i],r[i]-a[i]));
sp[1].push_back(make_pair(c[i],a[i]-l[i]));
}
if(sum1>s){
cout<<"impossible"<<endl;
continue;
}
if(sum3<s){
cout<<"impossible"<<endl;
continue;
}
int order = 0;
if(s>=sum2)order=0;
else order=1;
int sum4=abs(s-sum2);
int ans=0;
sort(sp[order].begin(),sp[order].end());
for(int i=0;i<sp[order].size();i++){
if(sum4>0){
int d=min(sum4,sp[order][i].second);
sum4-=d;
ans+=d*sp[order][i].first;
}
}
cout<<ans<<endl;
}
}
喵哈哈村与哗啦啦村的大战（四）
树形dp
维护dp1[i]表示从下到上大于等于的序列个数。
维护dp2[i]表示从下到上小于等于的序列个数。
这两者相乘，就是好序列的个数。
但是这有重复的项，因为都统计了相等的，所以得减去相等的与相等的之乘积。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
vector<pair<int,int> >E[maxn];
int n,a[maxn];
long long Down[maxn],Up[maxn],Down2[maxn],Up2[maxn];
long long equ[maxn];
long long ans = 0;
void dfs(int x,int fa){
Down[x]=1;
Up[x]=1;
Down2[x]=1;
Up2[x]=1;
equ[x]=1;
long long sumup,sumdown,sumequ;
for(int i=0;i<E[x].size();i++){
int v = E[x][i].second;
if(v==fa)continue;
dfs(v,x);
if(a[x]>=a[v]){
Down[x]+=Down[v];
}
if(a[x]<=a[v]){
Up[x]+=Up[v];
}
if(a[x]==a[v]){
equ[x]+=equ[v];
}
}
sumup=Up[x];
sumdown=Down[x];
sumequ=equ[x];
for(int i=0;i<E[x].size();i++){
int v = E[x][i].second;
if(v==fa)continue;
if(a[x]<=a[v]){
sumup-=Up[v];
}
if(a[x]>=a[v]){
sumdown-=Down[v];
}
if(a[x]==a[v]){
sumequ-=equ[v];
}
if(a[x]>=a[v])
ans+=Down[v]*sumup;
if(a[x]<=a[v])
ans+=Up[v]*sumdown;
if(a[x]==a[v])
ans-=equ[v]*sumequ;
}
}
int main(){
while(scanf("%d",&n)!=EOF){
ans=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),E[i].clear();
for(int i=1;i<n;i++){
int A,B;
scanf("%d%d",&A,&B);
E[A].push_back(make_pair(a[i],B));
E[B].push_back(make_pair(a[i],A));
}
for(int i=1;i<=n;i++)
sort(E[i].begin(),E[i].end());
dfs(1,-1);
cout<<ans<<endl;
}
}
喵哈哈村与哗啦啦村的大战（五）
假设现在考虑到第i个数，第i个数是12=223，那么m[j]统计前i-1个数，前缀为j的个数。
那么gcp为2的答案就是m[2]-m[4]
看懂这个这道题就简单了，自己写就好了。
#include<bits/stdc++.h>
using namespace std;
map<int,int> H;
int n;
int a[100005];
int main(){
while(cin>>n){
H.clear();
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
long long ans = 0;
for(int i=0;i<n;i++){
vector<int>tmp;
int now=1;
tmp.push_back(now);
for(int j=2;j*j<=a[i];j++){
while(a[i]%j==0){
now*=j;
tmp.push_back(now);
a[i]/=j;
}
}
if(a[i]!=1){
now*=a[i];
tmp.push_back(now);
}
reverse(tmp.begin(),tmp.end());
long long sum = 0;
for(int j=0;j<tmp.size();j++){
ans+=1ll*tmp[j]*(1ll*H[tmp[j]]-sum);
sum=H[tmp[j]];
H[tmp[j]]++;
}
}
cout<<ans<<endl;
}
}