比赛链接: 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.今天也全力以赴,守护着世界

思路

贪心的想,我们如果想让代价最小,那么我们肯定是希望删除负数的时候使用ai×ia_i \times i 在它原本的位置的价值从后往前来删除,而对于正数,我们直接在第一个位置删除即可。

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...