【题解】hyy和tgt的国庆信心赛

haphyxlos 2020-10-04 9:08:49

#A 签到题,因为数据范围较大,所以转换思路用字符串存。存完后再记一个cnt累加下每一位的值,最后判断cnt能否被9整除即可。核心代码如下:

ll ans=0;
for(ll i=0;i<s.size();++i)ans=ans+(s[i]-'0');
if(ans%9==0)puts("YES");
else puts("NO");

#B 思维题,手推规律即可。但鉴于本题大家普遍未获得理想的分数,顾放出标解。标解如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const double eps=1e7-8;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int maxm=1e6+5;
string s;
int n,cur=9;
bool f=true;
vector<bool> v;
char in[105],out[105];
int main(int argc, char const *argv[]){
	std::ios::sync_with_stdio(false);
	cin>>s;
    n=s.size();
    v.resize(n);
    for(int i=n-1;i>=0;--i){
        v[i]=f;
        if(s[i]!='9')f=false;
    }
    for(int i=0;i<n;++i){
        if(s[i]=='0')continue;
        if(v[i])cur=min(cur,max(1,s[i]-'0'));
        else cur=min(cur,max(1,s[i]-'0'-1));
    }
    printf("%d\n",cur);
	return 0;
}

#C 数论题,错排问题。核心代码如下:

a[1]=0,a[2]=1;
for(int i=3;i<=20;++i)a[i]=(i-1)*(a[i-2]+a[i-1]);

#D 思维题,自己推规律。但鉴于本题大家普遍未获得理想的分数,顾放出标解。标解如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const double eps=1e7-8;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int maxm=1e6+5;
int main(int argc, char const *argv[]){
	int n;
	scanf("%d",&n);
	if(n%2==0)printf("%lld",(1LL<<n)+2);
	else printf("%lld",(1LL<<n)-2);
	return 0;
}

#E 数论题,整除分块。但鉴于本题大家普遍未获得理想的分数,顾放出标解。标解如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const double eps=1e7-8;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int maxm=1e6+5;
int x,y;
ll ans; 
inline ll s(int k){
	ll i=1,j,sum=0;
	while(i<=k){
		j=k/(k/i);
		sum+=(k/i)*(i+j)*(j-i+1)/2;
		i=j+1;
	}
	return sum;
}
int main(int argc, char const *argv[]){
	std::ios::sync_with_stdio(false);
	cin>>x>>y;
	cout<<s(y)-s(x-1);
	return 0;
}

#F 模板题,LCA。但鉴于本题数据,所以卡了倍增和RMQ,(但实际上这个数据不卡朴素解法……挺离谱的)(所以这题很对不起大家QwQ)但本题也有奆佬用了tarjan被卡,我只能说时间卡得紧,用快读啊!

共 1 条回复

Jack_Kasluo

裂开,我用tarjan被卡死了

AMAZE UI
Hello world!