Comet OJ - Contest #10
A 鱼目混珠
substr直接取后几位连续子串
#include <set> #include <map> #include <cmath> #include <queue> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; int main() { int t,ans=0; string s; scanf("%d",&t); while(t--) { cin>>s; int len=s.size(); if(len<5) continue; else { if(s.substr(len-5)=="acpty") ans++; } } printf("%d ",ans); return 0; }
B 沉鱼落雁
题的本质是插数字模拟，可以分成有出现3次的情况，没有出现3次的情况，没有出现3次的情况还可以分成出现2次和没出现2次的情况，没有出现2次中只要数出现1次的情况即可。
由于数的范围是1e9，用桶排计数感觉会超时，然后就用了离散化，将范围降到了1e5。
#include <set> #include <map> #include <cmath> #include <queue> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; vector<int> v; int a[100005],cnt[100005],cntt[5]; int find_key(int x) { return lower_bound(v.begin(),v.end(),x)-v.begin()+1; } int main() { int n,num; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); v.push_back(a[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1;i<=n;i++) { cnt[find_key(a[i])]++; } int ans=0; for(int i=1;i<=v.size();i++) { cntt[cnt[i]]++; } if(cntt[3]>0) { ans=cntt[3]-1+cntt[2]+cntt[1]/2; } else { if(cntt[2]>1) { ans=cntt[2]-1+cntt[1]; } else ans=cntt[1]; } printf("%d ",ans); return 0; }
EOJ Monthly 2019.9
这场感觉比comet这场有点难啊，一个签到substr，一个签到逆元，逆元之前还没有看过......
D 站军姿
一个被当作签到的逆元题......EOJ的比赛之前的没怎么写过，感觉div2难度？
晚上写了这场，之前没看过逆元，结果轻松愉快的爆零。这个题的概率公式可以在网上找到的，所以感觉大家都签了这个题。
没有卡在这概率公式上，结果被long long的最大范围卡了（也是傻, 2^(n-1)直接用1<<(n-1)算了......这必超long long啊，而且还没法mod，直接返回最后的结果了），以后说啥次方运算只用快速幂，乘一下mod一下真舒服。逆元我用的费马小定理直接套快速幂调用就行。最后注意特判1和2。
#include <map> #include <cmath> #include <queue> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; const int mod=1000000007; ll qkpow(ll a,ll b) { ll ans=1; a=a%mod; while(b) { if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans%mod; } int main() { int t; ll n; scanf("%d",&t); while(t--) { scanf("%lld",&n); if(n==1 || n==2) printf("1 "); else { ll temp=qkpow(2,n-1); n=n%mod; printf("%lld ",n*qkpow(temp,mod-2)%mod); } } return 0; }
A 才艺展示
博弈最后输赢推导虽然看了sg函数，但这个我不会写，我太菜了。
所以这个就是看题解结论写的。
#include <map> #include <cmath> #include <queue> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; int main() { int t; ll n,cnt=1; scanf("%d",&t); while(t--) { bool flag=false; scanf("%lld",&n); while(n>0) { if((cnt & 1) && (n & 1)) { flag=true; break; } n=n>>1; cnt++; } if(flag) printf("Little Fang Win "); else printf("Cuber QQ Win "); } return 0; }