合肥学院ACM集训队第一届暑假友谊赛 B FYZ的求婚之旅 D 计算机科学家 F 智慧码题解...

刺骨的言语ヽ痛彻心扉 2021-12-13 03:57 161阅读 0赞

比赛网址：[https://ac.nowcoder.com/acm/contest/994\#question][https_ac.nowcoder.com_acm_contest_994_question]

B FYZ的求婚之旅  
  
思路：  
  
![1578720-20190712175019583-783145957.png][]

然后用快速幂即可。

细节见代码：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define rt return #define dll(x) scanf("%I64d",&x) #define xll(x) printf("%I64d\n",x) #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ int main() { //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin); //freopen("D:\\common_text\code_stream\\out.txt","w",stdout); const ll mod=1e9+7ll; ll n,m; cin>>n>>m; ll ans=powmod(m+1ll,n,mod); cout<<ans<<endl; return 0; } inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ' ' || ch == '\n'); if (ch == '-') { *p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } } }

D 计算机科学家  
  
思路：  
  
19=16+2+1  
而在二进制数后面加4个0，就等于这个数乘以16。  
加一个0，就等于这个数乘以2

然后三个二进制字符串相加即可。  
二进制字符串相加，只有3种状态，两个1，两个0，一个1和一个0。  
枚举下情况就好了，维护一个进位状态。

细节见代码：

#include<bits/stdc++.h> using namespace std; string add(string a,string b) { int len1=a.size(),len2=b.size(); if(len1>len2)swap(a,b),swap(len1,len2); reverse(a.begin(),a.end());reverse(b.begin(),b.end()); for(int i=0;i<len2-len1;i++)a+="0"; int f=0; string ans=""; for(int i=0;i<len2;i++){ int k=a[i]-'0'+b[i]-'0'+f;f=0; if(k>=2)k%=2,f=1; if(k==0)ans+="0"; else ans+="1"; } if(f)ans+="1"; reverse(ans.begin(),ans.end()); return ans; } int main(){ std::ios::sync_with_stdio(false); int n; cin>>n; string s; cin>>s; string s4=s+"0000",s2=s+"0"; s=add(s,s4); s=add(s,s2); cout<<s<<endl; return 0; }

F 智慧码  
  
思路：

STL的基础应用。

用STL写很方便，  
map来维护每一个数字对应的字符串信息，  
用string类的自带函数来处理前导0。

细节见代码：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define rt return #define dll(x) scanf("%I64d",&x) #define xll(x) printf("%I64d\n",x) #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ map<int,string> m; int n; int a[maxn]; string rm0(string s){// 去除前导0函数 int i; for(i=0;i<s.size()-1;i++) if(s[i]!='0') break; return s.substr(i); } int main() { m[0]="0000"; m[1]="0001"; m[2]="0010"; m[3]="0011"; m[4]="0100"; m[5]="0101"; m[6]="0110"; m[7]="0111"; m[8]="1000"; m[9]="1001"; gbtb; cin>>n; string str; int x; repd(i,1,n) { cin>>x; str=""; int g=x%10; x/=10; int s=x%10; x/=10; int b=x%10; str=m[b]+m[s]+m[g]; reverse(ALL(str));// 反转字符串 cout<<rm0(str)<<endl; } return 0; } inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ' ' || ch == '\n'); if (ch == '-') { *p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } } }

转载于:https://www.cnblogs.com/qieqiemin/p/11177625.html

[https_ac.nowcoder.com_acm_contest_994_question]: https://ac.nowcoder.com/acm/contest/994#question
[1578720-20190712175019583-783145957.png]: /images/20211210/77b741399783401ebf22d9ca333eca02.png