比赛链接:https://vjudge.csgrandeur.cn/contest/506361#overview

A题:简单思维题

B题:水题

C题:大意是给出一个大数,q次操作,每次操作可以往后面+一个数或者-去一个末尾的数(整除10),每次操作输出这个大数mod 1e9+7

解决方法:
每次增加的操作是上一个模除后的数*10+这个数 再 mod ,每次减去的操作就上上一次的模除后的数。可以开一个数组记录每次模除后的数。再根据不同的操作进行运算。

这里还可以用费马小定理。我们记录这个大数,每次增加我们令r(模除后的数)*10+当前数%mod。然后增加一位到末尾。每次减少,我们可以先通过减去末尾数,这样我们希望再通过/10来获取一个新数,因为r在模运算中直接/10数据就会出现错误,所以我们应该乘以一个逆元来解决这个问题。
通过费马小定理:屏幕截图 2022-08-01 204119.png

我们可以得到  10^mod-2为一个逆元,因为我们要模拟一个除以10的操作。

记录r code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
const long long mod = 1e9+7;
vector<ll>ve;
int main()
{
//	ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
	string s;int q;
	cin>>s;
	cin>>q;
	ll r = 0;
	for(int i=0;i<s.size();i++)
	{
		r = (r*10+(s[i]-'0'))%mod;
		ve.push_back(r);
	}
	while(q--)
	{
		char c;int t;
		cin>>c;
		if(c=='+')
		{
			cin>>t;
			ll pos = (ve[ve.size()-1]*10+t)%mod;
			printf("%lld\n",pos);
			ve.push_back(pos);
		}else
		{
			
			ve.pop_back();
			printf("%lld\n",ve[ve.size()-1]);
		}
	} 
}


 

逆元code: 

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
const long long mod = 1e9+7;
vector<int>ve;
ll qpow(ll a,ll b)
{
	ll res = 1;
	while(b){
		if(b&1) res = res*a%mod;
		a = a*a%mod;
		b>>=1;
	}
	return res;
 } 
int main()
{
//	ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
	string s;int q;
	cin>>s;
	cin>>q;
	ll r = 0;
	for(int i=0;i<s.size();i++)
	{
		r = (r*10+(s[i]-'0'))%mod;
		ve.push_back(s[i]-'0');
	}
	while(q--)
	{
		char c;int t;
		cin>>c;
		if(c=='+')
		{
			cin>>t;
			ve.push_back(t);
			r = (r*10+t)%mod;
			printf("%lld\n",r%mod);
		}else
		{
			r = (r-ve[ve.size()-1]+mod)%mod;
			r = r*qpow(10,mod-2)%mod;
			ve.pop_back();
			printf("%lld\n",r%mod);
		}
	} 
}

G题:大意等同于给出一个数x,求1-x之间有多少数不包含  1,2,3,5,8

暴力大概会在test14超时,这里需要通过当前位数计算它一下的,知道遇到关键数字,在小区间内我们已经计算完了。
有用记忆化搜的,这种做法就不考虑了,烧脑~

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
const int nn = 2e5+10;
int t,n,a[nn];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int len = 0; 
		ll x ;
		cin>>x;
		x++;
		while(x){
			a[++len] = x%10;
			x/=10;
		}
		ll res = 0;
		for(int i=len;i>=1;i--)
		{
			ll cnt = 0;
			for(int j=0;j<a[i];j++){ //这里只考虑在这个数一下范围内的数,因为要计算范围内,所以x++ 
				if(j!=1&&j!=2&&j!=3&&j!=5&&j!=8)	cnt++;//为0的情况下相当于位数后面的数进行变化,这里只记录了变化了多少次。 
			}
			ll ans = 1;
			for(int j=1;j<=i-1;j++) ans*=5;//每个位数上的变化为5 
			res+=ans*cnt;
			if(a[i]==1||a[i]==2||a[i]==3||a[i]==5||a[i]==8)	break;//如果碰到关键数,在这个数以下的可能我们已经通过前面计算出来了 
		}
		cout<<res<<endl;
	}
}