A . Adjacent Squares （枚举）
枚举一下，满足题意则ans++即可
cin>>h>>w;
cin>>r>>c;
int ans=0;
for(int i=1;i<=h;++i)
for(int j=1;j<=w;++j)
{
if(abs(i-r)+abs(j-c)==1)
++ans;
}
cout<<ans;
B . Enlarged Checker Board （模拟）
模拟输出便可，注意循环的正确性。
cin>>n>>a>>b;
t=n;
flag=1;
while(t--)
{
for(int k=1;k<=a;++k)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=b;++j)
{
if(flag)
{
if(i&1)
printf(".");
else
printf("#");
}
else
{
if(!(i&1))
printf(".");
else
printf("#");
}
}
printf("\n");
}
flag^=1;
}
C . Adjacent Swaps （模拟）
题意：每次操作给出一个数字，找到数字位置，将其和右边的数交换，如果是在最右边，则与左边的交换。
使用两个数组，一个数组a下标是位置，表示该位置目前的数字，另一个数组p下表是数字，表示该数字目前所处的位置。每次操作都维护这两个数组即可。
#include<bits/stdc++.h>
#define ll long long
const int N=1e6+5;
using namespace std;
int n,t;
int a[N],x;
int p[N];
int p1,x1;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
iota(a,a+n+1,0);
iota(p,p+n+1,0);
cin>>t;
while(t--)
{
cin>>x;
if(p[x]==n)
{
p1=p[x];
x1=a[p[x]-1];
swap(a[p[x]],a[p[x]-1]);
p[x1]=p1;
p[x]=p[x]-1;
}
else
{
p1=p[x];
x1=a[p[x]+1];
swap(a[p[x]],a[p[x]+1]);
p[x1]=p1;
p[x]=p[x]+1;
}
}
for(int i=1;i<=n;++i)
printf("%d ",a[i]);
}
D . 250-like Number (质数筛，枚举)
题意：二百五数是 $ p * q^3$ 其中p , q是质数且
p
<
q
p < q
p<q，对给出的N（
1
<
=
N
<
=
1
e
18
1<=N<=1e18
1<=N<=1e18），求有多少个二百五数。（这个二百五应该是因为纪念abc250哈哈哈）
我们先用线性筛筛出一定范围内的质数，因为N的范围很大，所以我们也尽量筛多一点，最后我们枚举出$ p * q^3$的值，因为这个值有可能溢出，我们可以将质数之一移向右边。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
ull prime[20000005];
int cnt;
bool isprime[20000005];
void shai(ull x)
{
for(int i=2;i<=x;i++)
{
if(isprime[i])
prime[++cnt]=i;
for(int j=1;j<=cnt,i*prime[j]<=x;j++)
{
isprime[i*prime[j]]=0;
if(i%prime[j]==0)
break;
}
}
}
ull n,t;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ull sum=0;
memset(isprime,1,sizeof(isprime));
shai((ull)20000000);
cin>>n;
for(int i=1;i<=cnt;++i)
for(int j=i+1;j<=cnt;++j)
{
if(prime[i]*prime[j]*prime[j]>(n/prime[j]))
break;
++sum;
}
printf("%lld\n",sum);
}
E . Prefix Equality （哈希）
题意：给出两段整数序列a,b，接着是q次询问，询问给出两个整数x,y，问a的前x位数字和b的前y位数字种类是否完全相同。
思路: 注意到这道题是问前若干位的数字种类相同，因此遍历一遍数列，如果出现了新的数，则计算其哈希值加入其中，若已经出现过了，就不需要加入了，以此来去除重复数字对序列种类哈希值的影响，最后在询问中查询是否相等即可。
#include<bits/stdc++.h>
#define ll long long
const int N=2e5+5;
using namespace std;
int n,t;
set<int>s1,s2;
unsigned int h1[N],h2[N];
int r=1e9+7;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int x,y;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>x;
if(!s1.count(x))
h1[i]=h1[i-1]+x*(x+r);
else
h1[i]=h1[i-1];
s1.insert(x);
}
for(int i=1;i<=n;++i)
{
cin>>x;
if(!s2.count(x))
h2[i]=h2[i-1]+x*(x+r);
else
h2[i]=h2[i-1];
s2.insert(x);
}
cin>>t;
while(t--)
{
cin>>x>>y;
if(h1[x]==h2[y])
printf("Yes\n");
else
printf("No\n");
}
}
F . One Fourth （计算几何）
官方题解利用滑动窗口优化到了
O
(
N
)
O(N)
O(N), 大概意思是说先选取第二个点作为q，然后对
p
=
1
,
2
,
3..
N
p=1,2,3..N
p=1,2,3..N进行遍历，计算吃的
p
,
q
,
q
+
1
p,q,q+1
p,q,q+1面积，如果吃的面积
E
<
S
/
4
E<S/4
E<S/4，使q上升，在循环结束时移除
p
,
p
+
1
,
q
p,p+1,q
p,p+1,q即可。而不需要重新从
q
=
2
q=2
q=2开始，因为可以证明这样不会使结果更优。
官方sample code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Point
{
ll px,py;
};
Point operator+(const Point& a1,const Point& a2)
{
return Point{a1.px+a2.px,a1.py+a2.py};
}
Point operator-(const Point& a1,const Point& a2)
{
return Point{a1.px-a2.px,a1.py-a2.py};
}
bool operator<(const Point& a1, const Point& a2)
{
if (a1.px<a2.px) return true;
if (a1.px>a2.px) return false;
if (a1.py<a2.py) return true;
return false;
}
ll crs(Point p1,Point p2)
{
return p1.px*p2.py-p1.py*p2.px;
}
int main()
{
int n;
cin>>n;
vector<Point>pts(n);
for(int i=0;i<n;i++)
cin>>pts[i].px>>pts[i].py;
ll s=0;
for(int i=2;i<n;i++)
s+=abs(crs(pts[i-1]-pts[0],pts[i]-pts[0]));
ll res=8e18,e=0;
int q=1;
for(int p=0;p<n;p++)
{
while(4*e<s)
{
e+=abs(crs(pts[q]-pts[p],pts[(q+1)%n]-pts[p]));
q++;
q%=n;
res=min(res,abs(4*e-s));
}
e-=abs(crs(pts[p]-pts[q],pts[(p+1)%n]-pts[q]));
res=min(res,abs(4*e-s));
}
cout<<res<<'\n';
}
G . Stonks（反悔贪心）
全新股票买卖，现已加入股票买卖豪华午餐。
我们在遇到比目前最低价格高的股票时就进行买入卖出操作，这是贪心。但是如果后来又来了一个更高价格的呢，我们就买入此时卖出的，达到反悔的效果。也就是比如说，对于
p
<
q
<
r
p<q<r
p<q<r我以p的价格买入，后来q的价格贪心卖出，那么我接着以q的价格买入, 再以r的价格卖出。 这一连串的操作， 其实相当以p的价格买入，以r的价格卖出。我们用优先队列实现这一操作。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,t;
ll ans,x;
priority_queue<ll,vector<ll>,greater<ll>>q;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
ans=0;
for(int i=1;i<=n;++i)
{
cin>>x;
if(!q.empty()&&q.top()<x)
{
ans+=x-q.top();
q.pop();
q.push(x);
}
q.push(x);
}
printf("%lld\n",ans);
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
