abc254_a
题目翻译
输入一个数，输出它的后两位。
题目思路
思路一
int 读入，要特判前导零。
思路二
char 读入，直接输出。
我写的是 int 读入。
AC 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
if (n / 10 % 10 == 0)
{
cout << 0 << n % 10 << endl;
}
else
{
cout << n % 100 << endl;
}
return 0;
}abc254_b
题目翻译
杨辉三角。
题目思路
算得上 dp 初学入门题（？
状态转移方程：$dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}$。
特判一下 $n=1$，$dp_{1,1}=1$。
AC 代码
#include<bits/stdc++.h>
using namespace std;
int a[35][35];
int main()
{
int n;
cin >> n;
a[1][1] = 1;
cout<<1<<endl;
for (int i = 2; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}abc254_c
题目翻译
输入一个数组，只有下标之差恰好是 $k$ 的两个位置才能交换。
可以交换任意多次。
问能不能让数组变成升序。
题目思路
其实就是 $i \bmod k$ 相同的，可以互换。
我们考虑把这一串数组，按 $i\bmod k$ 的值，把它变成一个二维数组。
举个栗子：
10 3
1 2 3 4 5 6 7 8 9 10按 $i \bmod k$ 分类，即为：
等于1：1 4 7 10
等于2：2 5 8
等于0：3 6 9然后横向排列，最后组合在一起，形成一维数组。
如果组合起来是升序的，也就可以升序。
AC 代码
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main()
{
int n, k;
cin >> n >> k;
vector<int>v[k + 5];
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
v[i % k == 0 ? k : i % k].push_back (x);
}
for (int i = 1; i <= k; i++)
{
sort (v[i].begin(), v[i].end());
int cnt = 1;
for (int j = 0; j < v[i].size(); j++)
{
a[cnt + i - 1] = v[i][j];
cnt += k;
}
}
puts (is_sorted (a + 1, a + n + 1) ? "Yes" : "No");
return 0;
}abc254_d
题目翻译
问有多少 $i,j$，$i,j\leq n$ 且 $i\times j$ 为完全平方数。
题目思路
很有趣的思维题。
我们考虑把每个完全平方数，看成 $x\times \gcd(i,j)\times y\times gcd(i,j)$。
当然，这里 $x$ 和 $y$ 也必须是完全平方数。
如果只是 $x\times y$ 是完全平方数，不是自己是完全平方数，还要拆干嘛？又回到第一步
我们考虑把每个完全平方数，看成 $x\times \gcd(i,j)\times y\times gcd(i,j)$。
了。
当然，这里的 $i=x\times\gcd(i,j),j=y\times\gcd(i,j)$。
显然，$\gcd(x,y)=1$，不然这个最大公因数就求错了，不满足 $i=x\times\gcd(i,j),j=y\times\gcd(i,j)$。
所以，$x,y$ 分别为两个互质的完全平方数。
我们只需枚举 $x,y$。
枚举后，自然也会发现，这里的 $\gcd(i,j)$ 会有很多选择。
$\gcd(i,j)$ 最大的可能是 $\left\lfloor\dfrac{n}{\max(x,y)}\right\rfloor$。
所以，我们枚举每组 $x,y$，加上 $\left\lfloor\dfrac{n}{\max(x,y)}\right\rfloor$ 即为答案。
放个伪代码：
for(1~sqrt(n))
生成完全平方数
for(1~完全平方数个数)
for(1~完全平方数个数)
if(两个完全平方数互质)
加上可能的gcd，也就是 n/较大的完全平方数AC 代码
#include<bits/stdc++.h>
using namespace std;
int a[1000],sz;
int main()
{
int n;
long long ans=0;
cin>>n;
for(int i=1;i<=sqrt(n);i++)
{
a[++sz]=i*i;
}
for(int i=1;i<=sz;i++)
{
for(int j=1;j<=sz;j++)
{
if(__gcd(a[i],a[j])==1)
{
ans+=n/max(a[i],a[j]);
}
}
}
cout<<ans<<endl;
return 0;
}abc254_e
题目翻译
输入一个图，每个点度数至多是 $3$。
$Q$ 个询问，每次问到点 $x$ 的距离小于等于 $k$ 的点，所有点的标号之和。
$k$ 至多是 $3$。
题目思路
就是个搜索。
因为度数 $\leq 3$，所以每个点连接的点数不会超过 $40$。
但有个问题，正常搜索，需要 vis 数组，所以每次清空会超时。
我们考虑用一个 set 存下点坐标。
最后相加即为答案。
AC 代码
#include<bits/stdc++.h>
using namespace std;
vector<int>a[150005];
set<int>vis;
void dfs (int dep, int k, int x)
{
if (dep > k)
{
return;
}
vis.insert (x);
for (auto i : a[x])
{
dfs (dep + 1, k, i);
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
a[x].push_back (y);
a[y].push_back (x);
}
int q;
cin >> q;
while (q--)
{
vis.clear();
int x, k, ans = 0;
cin >> x >> k;
dfs (0, k, x);
for (int i : vis)
{
ans += i;
}
cout << ans << endl;
}
return 0;
}