- SWPU ROUND #6(DIV.3)
SWPU ROUND #6(DIV.3)题解
- 2021-12-26 17:44:13 @
比赛链接: http://acm.mangata.ltd/contest/61c6d49baeb5956282ee7cba
A.我只知道,在我心里,比起这个世界,你更重要!
思路
签到题,我们只用计算琪亚娜在死之前能打出多少伤害即可,然后将其与芽衣的生命值做对比
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[4];
int main()
{
int t;
scanf("%d",&t);
while(t--) {
for(int i = 0;i < 4; ++i) {
scanf("%lld",&a[i]);
}
ll keyq = (a[3]/a[0] + 1LL)*a[1];
if(a[3] % a[0] == 0) keyq -=a[1]; //这里是特判一下如果芽衣的攻击为1的情况
if(keyq >= a[2]) puts("YES");
else puts("NO");
}
return 0;
}
B.为世界上所有的美好而战
思路
开始样例给的有问题,后面更改了,很显然1到n的排列本身就是两两互质,所以直接输出n即可
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n;
cin>>n;
cout<<n;
return 0;
}
C.今天也全力以赴,守护着世界
思路
贪心的想,我们如果想让代价最小,那么我们肯定是希望删除负数的时候使用 在它原本的位置的价值从后往前来删除,而对于正数,我们直接在第一个位置删除即可。
Code
#include<bits/stdc++.h>
#include<ctime>
#include<cstdlib>
using namespace std;
#define ll long long
int main()
{
ll n,k;
scanf("%lld",&n);
ll sum = 0;
for(int i = 1;i <= n; ++i) {
scanf("%lld",&k);
if(k < 0) sum += k*i;
else sum += k;
}
printf("%lld\n",sum);
return 0;
}
D.我已经做出了我的选择
思路
思路一
直接无脑快速幂,求就完事,然后注意一下数据大于等于27的时候
思路二
直接打标,我们能发现当n大于等于27的时候我们直接输出134217727即可,这是由于这个模数是2的幂,感兴趣可以去试一试
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 134217728;//27
ll ksm(ll a,ll b) {
ll ans = 1;
for(;b;b>>=1LL) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
int main()
{
ll n ;
scanf("%lld",&n);
ll ans = (ksm(2LL,n)-1+mod)%mod;
printf("%lld\n",ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 134217728;//27
int main()
{
ll n ;
scanf("%lld",&n);
if(n >= 27) puts("134217727");
else{
ll ans = 1;
while(n--) ans *= 2;
printf("%lld\n",ans-1);
}
return 0;
}
E.善恶错乱之世,同病相怜之人
思路
很显然一眼看过去就是一道很经典的二维偏序问题,我们通过对询问存储下来然后升序排序,通过线段树或者树状数组更新并离线询问即可
Code
#include<bits/stdc++.h>
#include<ctime>
#include<cstdlib>
using namespace std;
#define ll long long
const int N = 5e5+10;
ll tree[N],a[N],ans[N],vis[N];
ll n,m;
struct Node {
int pos,l,r;
}V[N];
ll lowbit(ll x) {
return -x & x;
}
void updata(ll x,ll k) {
while(x <= n) {
tree[x] += k;
x += lowbit(x);
}
}
ll query(ll x){
ll ans = 0;
while(x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i = 1;i <= n; ++i) {
scanf("%lld",&a[i]);
}
ll l,r;
for(ll i = 1;i <= m; ++i) {
scanf("%lld%lld",&l,&r);
V[i].l = l;
V[i].r = r;
V[i].pos = i;
}
sort(V+1,V+1+m,[](Node a,Node b){return a.r == b.r?a.l < b.l:a.r < b.r;});
ll loc = 1;
for(ll i = 1;i <= m; ++i) {
for(ll j = loc;j <= V[i].r; ++j) {
if(vis[a[j]]) updata(vis[a[j]],-a[j]);
vis[a[j]] = j;
updata(j,a[j]);
}
loc = V[i].r + 1;
ans[V[i].pos] = query(V[i].r) - query(V[i].l - 1);
}
for(ll i = 1;i <= m; ++i) {
printf("%lld\n",ans[i]);
}
return 0;
}
后记
前三题还是比较简单,第四题稍微难一点点,但是只要细心观察还是能做出来的。总体而言还是达到了预期,有人AK、大部分人出题
0 comments
No comments so far...