T1.金币
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int k;
long long ans;
int main()
{
scanf("%d",&k);
int cnt=;
while(k)
{
for(int i=;i<=cnt;i++)
{
if(k==)break;
ans+=cnt;k--;
}
cnt++;
if(k==)break;
}
printf("%lld",ans);
return ;
}
T2.扫雷游戏
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int xx[]={-,,,-,,-,,},yy[]={-,-,-,,,,,};
int n,m;
char s[][];
int count(int x,int y)
{
int num=;
for(int i=;i<;i++)
{
int xi=x+xx[i],yi=y+yy[i];
if(xi<||xi>=n||yi<||yi>=m)continue;
if(s[xi][yi]=='*')num++;
}
return num;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)scanf("%s",s[i]);
for(int i=;i<n;i++,printf("\n"))
for(int j=;j<m;j++)
{
if(s[i][j]=='*')printf("*");
else printf("%d",count(i,j));
}
return ;
}
T3.求和
仔细读题之后我们会发现，我们枚举的过程其实跟y没什么关系……
但因为题目限定了x+z=2*y，即x+z为偶数，所以x和z必须同奇或同偶。
所以分颜色分奇偶存一下就好了✔
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=;
long long ans;
int n,m,siz,color,num[N];
vector<int>a[N][];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int main()
{
n=read();m=read();
for(int i=;i<=n;i++)num[i]=read();
for(int i=;i<=n;i++)
{
color=read();
a[color][i%].push_back(i);
}
for(int i=;i<=m;i++)
{
for(int t=;t<;t++)
{
siz=a[i][t].size();
for(int j=;j<siz;j++)
for(int k=j+;k<siz;k++)
{
int x=a[i][t][j],z=a[i][t][k];
ans=(ans+(long long)(x+z)*(num[x]+num[z]))%;
}
}
}
printf("%lld",ans);
return ;
}
T4.推销员
维护两个大根堆，一个存各个住户的距离*2+疲劳值，另一个存各个住户的疲劳值；每次取出堆顶元素，将较大的那一个累加进答案里。
注意判断是否合法：假设当前走到的距离最远的住户为x；则直接累加住户i的疲劳值需要满足的条件为：s[i]<=s[x]；累加住户i的距离*2+疲劳值需要满足的条件为：s[i]>s[x]，且累加时记得减去s[x]*2。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=;
struct node
{
int w,pos;
bool operator <(const node& a)const{return w<a.w;}
}q2[N],r1,r2;
priority_queue<node>q1;
int n,cnt,cut,tail,s[N],t[N];
bool f[N];
long long ans;
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int main()
{
n=read();cnt=n;tail=n;
for(int i=;i<=n;i++)s[i]=read();
for(int i=;i<=n;i++)
{
t[i]=read();
q2[i].w=s[i]*+t[i];q2[i].pos=i;
}
sort(q2+,q2+n+);
while(cnt)
{
if(tail)r2=q2[tail],tail--;
else r2=(node){,n+};
if(r2.pos<=cut)continue;
if(!q1.empty())r1=q1.top(),q1.pop();
else r1=(node){,};
if(r1.w>r2.w-*s[cut])
{
ans+=r1.w;
if(r2.pos!=n+)tail++;
}
else
{
ans+=r2.w-*s[cut];
for(int i=cut+;i<r2.pos;i++)q1.push((node){t[i],i});
if(r1.pos!=)q1.push(r1);
cut=r2.pos;
}
printf("%lld\n",ans);cnt--;
}
return ;
}