A-Simple Calculator
题意：
给了两个数x，y。现在给你两个按钮，按钮A将x+1，按钮B将x的符号翻转，问最少要多少次操作，使x=y。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int x,y;
int main()
{
scanf("%d%d",&x,&y);
if(x>0&&y>0)
{
if(x>y)
printf("%d",x-y+2);
else
printf("%d",y-x);
}
else if(x>0&&y<0)
{
if(x>-y)
printf("%d",1+x+y);
else
printf("%d",1-x-y);
}
else if(x<0&&y<0)
{
if(x<y)
printf("%d",y-x);
else
printf("%d",2+x-y);
}
else if(x<0&&y>0)
{
if(-x>y)
printf("%d",1-x-y);
else
printf("%d",1+x+y);
}
else if(x==0)
{
if(y>=0)
printf("%d",y);
else
printf("%d",1-y);
}
else
{
if(x>0)
printf("%d",1+x);
else
printf("%d",-x);
}
return 0;
}
B-Contiguous Repainting
题意：
给了你一个长度为n的数组，每次你能将连续k个数涂成黑色或白色，可覆盖，可以填任意多次，问黑色方块上的数加起来最多为多少。
solution：
根据题意分析，可以知道可以先取出k个数特判，其余的只要贪心的取正数即可。因此先将正数的和求出来，然后每k个数判断一下加上负数和或者去掉正数和哪种情况更优，取个max。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n,k;
int a[100005];
ll maxn=0,tem=0;
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]>0)tem+=a[i];
}
ll zh=0,fu=0;
for(int i=0;i<k;i++)
{
if(a[i]>0)zh+=a[i];
else fu+=a[i];
}
if(zh>-fu)maxn=max(maxn,tem+fu);
else maxn=max(maxn,tem-zh);
for(int i=k;i<n;i++)
{
if(a[i-k]>0)zh-=a[i-k];
else fu-=a[i-k];
if(a[i]>0)zh+=a[i];
else fu+=a[i];
if(zh>-fu)maxn=max(maxn,tem+fu);
else maxn=max(maxn,tem-zh);
}
printf("%lld",maxn);
return 0;
}
C-Tetromino Tiling
题意：
给出几种俄罗斯方块的个数，让你求最多用k个俄罗斯方块能拼成高度为2，长为2k的矩形。矩形必须是实心的。
solution：
先求出如何用俄罗斯方块拼成完整的矩形。发现第三个、第六个、第七个没有用处。2个第一种；或1个第二种；或2个第四种；或2个第五种，或奇数个第一种，1个第四种，1个第五种；或偶数个第一种，2个第四种；或偶数个第一种，2个第五种。
然后贪心求解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
ll a[10];
int main()
{
for(int i=0;i<7;i++)scanf("%lld",&a[i]);
ll res=0;
res=a[0]/2*4+a[1]*2+a[3]/2*4+a[4]/2*4;
if(a[0]%2)
{
if(a[3]&&a[4])
{
if(a[3]%2==1&&a[4]%2==1)
res+=6;
else if(a[3]%2==1)
res+=2;
else if(a[4]%2==1)
res+=2;
}
}
else if(a[0])
{
if(a[3]%2==1&&a[4]%2==1)
res+=2;
}
printf("%lld",res/2);
return 0;
}
D-K-th K
题意：
给了你一个长度为n的数组x，让你构造一个数组使得i第i次出现的位置在 x i x_i xi位置上，1-n的每个数都出现n次。
solution：
贪心。先将数组x按从小到大排序，然后先在 x i x_i xi位置上放上原来的下标的那个数，然后再从vis数组中从前往后枚举，放入相应数字（而不能从 x i x_i xi往前枚举，因为这样前面就可能出现空位，后面的数就不能放了），枚举完所有的x后。然后类似的贪心枚举后面的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n;
struct node
{
int x,id;
bool operator <(const node pp)const
{
return x<pp.x;
}
}p[505];
int vis[300005];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i].x);
p[i].id=i;
}
sort(p+1,p+1+n);
memset(vis,0,sizeof(vis));
bool flag=true;
for(int i=1;i<=n;i++)
{
int pos=p[i].x;
int c=p[i].id-1;
if(vis[pos])flag=false;
vis[pos]=p[i].id;
pos=1;
while(pos<p[i].x)
{
if(c==0)break;
if(vis[pos]){
pos++;continue;}
vis[pos++]=p[i].id;
c--;
}
if(c>0){
flag=false;break;}
}
for(int i=1;i<=n;i++)
{
int pos=p[i].x+1;
int c=n-p[i].id;
while(pos<=n*n)
{
if(c==0)break;
if(vis[pos]){
pos++;continue;}
vis[pos++]=p[i].id;
c--;
}
if(c>0){
flag=false;break;}
}
if(flag)
{
printf("Yes\n");
for(int i=1;i<=n*n;i++)printf("%d ",vis[i]);
}
else printf("No");
return 0;
}
E-Next or Nextnext
F-Black Radius
G-An Ordinary Game
题意：
给了一个字符串，你可以取出其中的一个字母的前提是，这个字符的两边还有字母，并且去掉这个字母后，断后重连的相邻两个字母不相同。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
string s;
int main()
{
cin>>s;
int n=s.length()-2;
if(s[0]==s[s.length()-1])n--;
if(n%2==0)printf("Second");
else printf("First");
return 0;
}
H-Cosmic Rays
题意：
给了起点和终点，以及n个圆圆心坐标和半径。问最短的从起点到终点的距离是多少（经过圆的那部分长度不算距离）。
solution:
另类的最短路。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int sx,sy,tx,ty,n;
struct node
{
int x,y,id,r;
double d;
bool operator>(const node pp)const
{
return d>pp.d;
}
}p[1005];
int vis[1005];
void dijktra()
{
priority_queue<node,vector<node>,greater<node>>que;
que.push(p[0]);
while(!que.empty())
{
node tem=que.top();que.pop();
if(vis[tem.id])continue;
vis[tem.id]=1;
for(int i=1;i<=n;i++)
{
if(i==tem.id)continue;
double dis=sqrt(1ll*(tem.x-p[i].x)*(tem.x-p[i].x)+1ll*(tem.y-p[i].y)*(tem.y-p[i].y));
if(dis>p[i].r+tem.r&&tem.d+dis-p[i].r-tem.r<p[i].d)
{
p[i].d=tem.d+dis-p[i].r-tem.r;
que.push(p[i]);
}
else if(dis<=p[i].r+tem.r&&tem.d<p[i].d)
{
p[i].d=tem.d;
que.push(p[i]);
}
}
}
}
int main()
{
scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
scanf("%d",&n);
p[0].x=sx;p[0].y=sy;p[0].d=0;p[0].id=0;p[0].r=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].r);
p[i].id=i;
p[i].d=1e18;
}
n++;
p[n].x=tx;p[n].y=ty;p[n].id=n;p[n].d=1e18;p[n].r=0;
dijktra();
printf("%.10f",p[n].d);
return 0;
}
I-Rotated Palindromes
J-Connectivity
题意：
给了你n个城市，k条路，l条高铁，问每个城市与几个城市是可达的（既要有路，又要有高铁），自己与自己也是可达的。
solution：
先分别对高铁和路进行并查集，然后寻找同一个点在哪两个集合，进行hash设置唯一标识，记录数量，只有标识相同代表这个城市与其他的标识相同的城市之间是可达的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n,k,l;
int f[200005],f1[200005];
ll ha=3e5;
map<ll,int>mp;
int Find(int fa[],int x){
return fa[x]==x?x:fa[x]=Find(fa,fa[x]);}
void Union(int fa[],int x,int y)
{
x=Find(fa,x);
y=Find(fa,y);
fa[x]=y;
}
int main()
{
scanf("%d%d%d",&n,&k,&l);
for(int i=1;i<=n;i++)f[i]=f1[i]=i;
for(int i=0;i<k;i++)
{
int u,v;scanf("%d%d",&u,&v);
Union(f,u,v);
}
for(int i=0;i<l;i++)
{
int u,v;scanf("%d%d",&u,&v);
Union(f1,u,v);
}
for(int i=1;i<=n;i++)
mp[1ll*ha*Find(f,i)+Find(f1,i)]++;
for(int i=1;i<=n;i++)
printf("%d ",mp[1ll*ha*Find(f,i)+Find(f1,i)]);
return 0;
}
京公网安备 11010502036488号