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();
}
|
