T1 打赌
https://gxyzoj.com/d/hzoj/p/3642
一道大模拟，容易发现，连续的4个数的和为14，这些直接求和，其余暴力处理即可
代码：
#include<cstdio>
#define ll long long
using namespace std;
int r,c,x[10]={1,6,4,3,2,5};
ll ans;
void Left()
{
int a=x[0],b=x[1],c=x[2],d=x[3];
x[0]=d,x[1]=c,x[2]=a,x[3]=b;
}
void Right()
{
int a=x[0],b=x[1],c=x[2],d=x[3];
x[0]=c,x[1]=d,x[2]=b,x[3]=a;
}
void Down()
{
int a=x[0],b=x[1],c=x[4],d=x[5];
x[0]=d,x[1]=c,x[4]=a,x[5]=b;
}
int main()
{
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++)
{
int t=c/4,s=c%4;
if(s==0) s=4;
ans=ans+1ll*t*14;
if(s<4) ans=ans+1ll*x[0];
for(int j=1;j<s;j++)
{
if(i%2) Right();
else Left();
if(j==1&&(s==2||s==3)) ans=ans+1ll*x[0];
if(j==2&&s==3) ans=ans+1ll*x[0];
}
Down();
}
printf("%lld",ans);
return 0;
}
T2 舞会
https://gxyzoj.com/d/hzoj/p/3643
先分类排序，很明显，身高相近的两个人配对更优，所以排序后用双指针统计答案即可
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ax[100005],ay[100005],bx[100005],by[100005];
int id1,id2,id3,id4,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
if(a>0) ax[++id1]=a;
else bx[++id2]=-a;
}
for(int i=1;i<=n;i++)
{
int b;
scanf("%d",&b);
if(b>0) ay[++id3]=b;
else by[++id4]=-b;
}
sort(ax+1,ax+id1+1);
sort(bx+1,bx+id2+1);
sort(ay+1,ay+id3+1);
sort(by+1,by+id4+1);
for(int i=1,j=0;i<=id1;i++)
{
// printf("%d ",ax[i]);
while(j<id4&&by[j+1]<=ax[i]) j++;
if(j<=id4&&by[j+1]>ax[i])
{
ans++,j++;
by[j]=0;
}
}
// printf("\n");
for(int i=1,j=0;i<=id3;i++)
{
// printf("%d ",ay[i]);
while(j<id2&&bx[j+1]<=ay[i]) j++;
if(j<=id2&&bx[j+1]>ay[i])
{
ans++,j++;
bx[j]=0;
}
}
printf("%d",ans);
return 0;
}
/*
3
1500 -1800 -1500
-1600 1900 -1700
*/
T3 最小生成树
https://gxyzoj.com/d/hzoj/p/3644
根据菊花图的情况，可以看出边权和最小为n-1，从题目可以看出，它满足小根堆性质，所以从小到大每次加点时，新点永远在叶子，再看回边权，因为每条边的权值都是1，所以两端的权值互质，所以答案就是：
\[ans=\prod_{i=2}^n \varphi(i) \]本蒟蒻没有想到欧拉函数的做法，浅附一份\(O(n\sqrt n)\)的容斥做法吧
#include<cstdio>
#define ll long long
using namespace std;
const int mod=1e8+7,N=20000;
int n,p[N+5],m,vis[N+5],num[N+5],cnt[N+5];
ll ans=1;
void prime()
{
for(int i=2;i<=N;i++)
{
if(!vis[i])
{
p[++m]=i;
num[i]=1;
}
//printf("%d",i);
for(int j=1;i*p[j]<=N&&j<=m;j++)
{
if(i%p[j]!=0&&vis[i]!=2)
{
vis[i*p[j]]=1;
num[i*p[j]]=num[i]+1;
}
else vis[i*p[j]]=2;
if(i%p[j]==0) break;
}
}
}
int main()
{
prime();
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
int tmp=0;
for(int j=2;j*j<=i;j++)
{
if(i%j==0)
{
if(vis[j]!=2)
{
if(num[j]%2) tmp+=cnt[j];
else tmp-=cnt[j];
}
cnt[j]++;
}
if(i%j==0&&j!=(i/j))
{
if(vis[i/j]!=2)
{
if(num[i/j]%2) tmp+=cnt[i/j];
else tmp-=cnt[i/j];
}
cnt[i/j]++;
}
}
cnt[i]++;
// for(int j=1;j<=n;j++)
// {
// printf("%d ",cnt[j]);
// }
// printf("\n");
ans=ans*(i-tmp-1)%mod;
// printf("%d %d\n",i,tmp);
}
printf("%d",ans);
return 0;
}
T4 买汽水
https://gxyzoj.com/d/hzoj/p/3645
折半搜索，前20个和后20个都搜1遍，统计情况，再用双指针统计答案
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,b[2],a[2][25],id[2],ans[2][2000005],res;
void dfs(int i,int x,int t)
{
if(t>m) return;
if(x==b[i]+1)
{
res=max(res,t);
ans[i][++id[i]]=t;
return;
}
dfs(i,x+1,t);
dfs(i,x+1,t+a[i][x]);
}
int main()
{
scanf("%d%d",&n,&m);
b[0]=n/2;
b[1]=n-b[0];
for(int i=1;i<=b[0];i++)
{
scanf("%d",&a[0][i]);
}
for(int i=1;i<=b[1];i++)
{
scanf("%d",&a[1][i]);
}
dfs(0,1,0);
// printf("1");
dfs(1,1,0);
sort(ans[0]+1,ans[0]+id[0]+1);
sort(ans[1]+1,ans[1]+id[1]+1);
for(int i=id[0],j=0;i>0;i--)
{
while(j<id[1]&&ans[0][i]+ans[1][j+1]<=m) j++;
if(ans[0][i]+ans[1][j]<=m)
{
res=max(res,ans[0][i]+ans[1][j]);
}
}
printf("%d",res);
return 0;
}