CDZSC_2022寒假个人训练赛21级(11)题解
-
简单
- B
- C
- G 字符串
-
中等
- D 贪心+字符串
- E DP
-
困难
- A 平方和定理+逆元（逆元（费马小定理））
- F 几何+枚举
以后很简单的题我就不写题解了，有需要问我。
A 矩形的数量 V3 51Nod - 3036
题解
（大家是不会算复杂度吗？看到一大堆人交一个for循环，也不看下数据范围有多大。 ）
第一眼还以为是简单题，虽然公式也挺好推的，但由于要用平方和定理+逆元还是算有点难。
首先易知题目要求我们求\(nm+(n-1)(m-1)+(n-2)(m-2)+...+(n-min(n,m))(m-min(n,m))\)的值。
设\(x=min(n,m)\)
有:$$nm+(n-1)(m-1)+(n-2)(m-2)+...+(n-x)(m-x)$$
根据平方和定理和等差数列求和有：
\[(x+1)nm+\frac{2x^3+3x^2+x}{6}-\frac{(n+m)(x+1)x}{2} \]答案就直接是这个公式了，\(O(1)\)复杂度，但要注意的是这题数据规模大(1e9)在运算中必然会超long long，要注意取模，并且该公式中有除法不能直接取模，要使用逆元，好在模数1e9+7是素数，可以直接使用费马小定理，以及带减法的取模要注意最后结果可能会是负数，最好在运算中加上个模数来保证答案为正。
（至于平方和定理和具体是啥我就不多写了，自己根据关键字查询，真要写起来就太多了。）
AC代码
#include
#include
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll pow(ll x, ll y, ll mod) {
ll ans = 1 % mod;
while (y) {
if (y & 1)ans = (ans*x) % mod;
x = (x*x) % mod;
y >>= 1;
}
return ans;
}
int main() {
ll n, m;
scanf("%lld%lld", &n, &m);
ll x = min(n, m);
ll inv6 = pow(6, mod - 2, mod);
//(6*(x+1)*n*m+2*x*x*x+3*x*x+x-3*(x+1)*x*(n+m))/6
ll ans = (6 * (x + 1)* n%mod*m%mod + 2 * x*x%mod*x%mod + 3 * x*x%mod + x - 3 * (x + 1)*x%mod*(n + m) % mod+mod) % mod*inv6%mod;
printf("%lld\n", ans);
return 0;
}
B Who's Opposite? CodeForces - 1560B
AC代码
#include
#include
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;
const ll mod = 1e9 + 7;
int p[N];
int main() {
int t, n,a,b,c;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &a,&b,&c);
int d = abs(a - b)-1;
n = d * 2 + 2;
int ans = (c + d) % n + 1;
if (n & 1||(ans==a&&c!=b)||(ans==b&&c!=a)||(a>n)||(b>n)||ans>n||c>n) {
printf("-1\n");
}
else {
printf("%d\n", ans);
}
}
}
C Infinity Table CodeForces - 1560C
AC代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include D Make a Power of Two CodeForces - 1560D
题意
两种操作
- 擦除一个数
- 向右加一位数
问，至少几次操作能把给定数变成2的次幂结果数字不能有前导零。
题解
先把2的次幂都预处理出来，然后将给出的数字和2的次幂一个个比对找最优，数据量都很小，不会超时。
AC代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include E USACO Number Triangles 计蒜客 - T3456
题解
简单dp
AC代码
#include
#include
using namespace std;
int dp[1005];
int main() {
int r, ans = 0,x;
scanf("%d", &r);
for (int n = 1; n <= r; n++)
for (int i = n; i>=1; i--){
scanf("%d", &x);
dp[i] = max(dp[i], dp[i - 1]) + x;
}
for(int i=0;i F New Year and Curling CodeForces - 908C
题意
向下丢圆，碰到底或者其他圆会停下，求一下每个圆最后停的位置的高度坐标。
题解
数据范围不大直接\(O(n^2)\)复杂度遍历。
AC代码
#include
#include
using namespace std;
struct node{
double x,y;
}s[1005];
int main(){
int n,r;
scanf("%d%d",&n,&r);
for(int i=0;i G 旋转字符串 51Nod - 1347
AC代码
#include
#include
#include
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
char s[1000005];
int cnt[26];
int main() {
while (~scanf("%s", s)) {
int flag = 1;
int n = strlen(s);
if (n & 1) {
flag = 0;
}
else {
for (int i = 0; i < n/2; i++) {
if (s[i] != s[i + n / 2]) {
flag = 0;
break;
}
}
}
printf("%s\n", flag ? "YES" : "NO");
}
}