2020牛客暑期多校训练营（第七场）
8.01 写模拟写哭了的牛客7
D-Fake News
题意
\sum^{n}_{i=1}i^2 一定不是完全平方数吗？
思路
只有 n=1 或 n=24 的时候结果是完全平方数，打表出来的。具体证明有个知乎回答？如何证明 1²+2²+…+n² 为平方数的解只有 n＝1 或 n＝24？
代码
#include<bits/stdc++.h>
#define scl(x) scanf("%lld", &x)
using namespace std;
typedef long long ll;
int solve(){
ll n; scl(n);
if(n==1||n==24) return puts("Fake news!");
return puts("Nobody knows it better than me!");
}
int main(){
ll _; scl(_); while(_--) solve();
}H-Dividing
题意
定义函数 f(n, k)，其中 1\leq n\leq N 、1\leq k\leq K。
初始有：f(1, k)=1 。有递推关系：
- f(n, k)=1 则 f(n+k, k)=1
- f(n, k)=1 则 f(n*k, k)=1
给定 N 、K ，问最多有多少对 f(n, k)=1
思路
很明显的数论分块。
首先 k>nf(1, k) 一种情况，加上后 k 可以直接取到 n。
之后分块讨论。对于每个为 i 的小块，先加上纯加法的方案 1+n/i-(n%i==0) 种。i>1n/i 种。大块同理，大块中的每个值 q 都有 2*i+1-(i*q==n) 的贡献。计算每个大块的个数，相乘一下。i*q==n 的情况只有一个，最后减去就行。
代码
#include<bits/stdc++.h>
#define pf printf
#define scl(x) scanf("%lld", &x)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int solve(){
ll n,k,ans(0); scl(n); scl(k);
if(k>n) ans+=k-n,k=n;
while(ans>=mod) ans-=mod;
for(int i=1;1ll*i*i<=n;++i){
if(i>k) break; ll t=n/i;
ans+=1+t; while(ans>=mod) ans-=mod;
if(n%i==0) ans--; while(ans<0) ans+=mod;
if(i>1){ ans+=t; while(ans>=mod) ans-=mod; }
// small
t=min(t,k); if(t==i) continue;
ll tmp=n/(i+1); if(t<=tmp) continue;
// 边界
ans+=1ll*(2ll*i+1)*(t-tmp)%mod; while(ans>=mod) ans-=mod;
if(t*i==n) ans--; while(ans<0) ans+=mod;
} return pf("%lld\n",ans);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}J-Pointer Analysis
题意
有 26 个全局指针，用 A-Z 表示；有 26 个对象，用 a-z 表示；每个对象还有 26 个成员变量，它们可以指向其他对象的指针，也用 a-z 表示。
有四种指令：
- A=x ，A 指向对象 x
- A=B ，A 可指向 B 指向的对象
- A.f=B ，A 指向的对象的成员变量 f 可指向 B 指向的对象
- A=B.f ，A 指向 B 指向的对象的成员变量 f 指向的对象
给出 n 条指令，这些指令重复多次且随机顺序地执行。问每个全局指针能指向的对象。
思路
题意很不清晰但是思路很清晰的带模拟。注意要迭代多次，看别人的直接再套了个 n 次的 for 就行了，那我赛时代码怎么不行啊
代码
#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
int mp1[30][30];
int mp2[30][30][30];
string s1[205],s2[205],t;
void solve(){
int n; cin>>n; rep(i,0,n) cin>>s1[i]>>t>>s2[i];
rep(_,0,n) rep(i,0,n){
int l1=s1[i].size(),l2=s2[i].size();
if(l1==1&&l2==1){
// A->o
if(islower(s2[i][0])) mp1[s1[i][0]-'A'][s2[i][0]-'a']=1;
// A->B
else rep(j,0,26) mp1[s1[i][0]-'A'][j]|=mp1[s2[i][0]-'A'][j];
}
else if(l1==3){
// (A.o.f)->B
rep(j,0,26) if(mp1[s1[i][0]-'A'][j]) rep(k,0,26)
mp2[j][s1[i][2]-'a'][k]|=mp1[s2[i][0]-'A'][k];
}
else{
// A->(B.o.f->C)
rep(j,0,26) if(mp1[s2[i][0]-'A'][j]) rep(k,0,26)
mp1[s1[i][0]-'A'][k]|=mp2[j][s2[i][2]-'a'][k];
}
}
rep(i,0,26){
cout<<(char)('A'+i)<<": ";
rep(j,0,26) if(mp1[i][j]) cout<<(char)('a'+j);
cout<<'\n';
}
}
int main(){
ios::sync_with_stdio(0); solve();
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录