2020牛客暑期多校训练营(第七场)

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; }
// 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$ 就行了,那我赛时代码怎么不行啊

代码

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