8.01 写模拟写哭了的牛客7
D-Fake News
题意
$\sum^{n}_{i=1}i^2$ 一定不是完全平方数吗?
思路
只有 $n=1$ 或 $n=24$ 的时候结果是完全平方数,打表出来的。具体证明有个知乎回答?如何证明 1²+2²+…+n² 为平方数的解只有 n=1 或 n=24?
代码
1 2 3 4 5 6 7 8 9 10 11 12
| #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>n$ 时肯定只有 $f(1, k)$ 一种情况,加上后 $k$ 可以直接取到 $n$。
之后分块讨论。对于每个为 $i$ 的小块,先加上纯加法的方案 1+n/i-(n%i==0)
种。$i>1$ 时,还需要考虑乘法一次后累加的情况 $n/i$ 种。大块同理,大块中的每个值 $q$ 都有 2*i+1-(i*q==n)
的贡献。计算每个大块的个数,相乘一下。i*q==n
的情况只有一个,最后减去就行。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #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; } 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(){ 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$ 就行了,那我赛时代码怎么不行啊
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #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){ if(islower(s2[i][0])) mp1[s1[i][0]-'A'][s2[i][0]-'a']=1; else rep(j,0,26) mp1[s1[i][0]-'A'][j]|=mp1[s2[i][0]-'A'][j]; } else if(l1==3){ 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{ 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(); }
|