比赛链接:https://vjudge.csgrandeur.cn/contest/506361#overview
A题:简单思维题
B题:水题
C题:大意是给出一个大数,q次操作,每次操作可以往后面+一个数或者-去一个末尾的数(整除10),每次操作输出这个大数mod 1e9+7
解决方法:
每次增加的操作是上一个模除后的数*10+这个数 再 mod ,每次减去的操作就上上一次的模除后的数。可以开一个数组记录每次模除后的数。再根据不同的操作进行运算。
这里还可以用费马小定理。我们记录这个大数,每次增加我们令r(模除后的数)*10+当前数%mod。然后增加一位到末尾。每次减少,我们可以先通过减去末尾数,这样我们希望再通过/10来获取一个新数,因为r在模运算中直接/10数据就会出现错误,所以我们应该乘以一个逆元来解决这个问题。
通过费马小定理:
我们可以得到 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; } }