1001. I love cube

题意

给定边长为 \(n - 1\) 的正方体,问正方体内部有多少个由格点组成的等边三角形,每条边都平行于正方体的一个面

分析

考虑格点全在正方体上的情况,边长为 \(n\) 的正方体,有 8 个满足条件的三角形。那么,对于边长为 \(n\) 的正方体,有 \((n-i)^3\) 个边长为 \(i\) 的正方体,每个正方体贡献为 8,而后得出答案为 \(8 * \sum_{i=1}^{i=n-1}{(n - i)^3} = 2 * (n(n - 1)) ^ 2\)

总结

被签到题 gank 了很久。。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7;
int T = 1;
const ll mod = 1e9 + 7;
void solve()
{
    ll n;
    scanf("%lld", &n);
    ll ans = (n % mod) * ((n - 1ll) % mod) % mod;
    ans = ans * ans % mod * 2ll % mod;
    printf("%lld\n", ans);
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
}

1004. I love counting

待补。。

1005. I love string

题意

给定一个字符串和一种操作,操作为顺次从字符串中选择一个字符插入正在构造的字符串的最前端或最后端,构造的字符串初始为空,问构造的串最后为最小的字典序有多少种构造方法

分析

真-签到题,不难发现只有给定的字符串最前面一段连续相同的字符可以随意前后摆放,剩下的都需要固定位置,否则不能保证最小字典序。因而答案为 \(2^{x-1}\)\(x\) 为最前方连续相同字符的长度

总结

一开始没仔细想,直接位运算算幂次,我是憨憨。。。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
int T = 1;
int n;
char s[N];
void solve()
{
   scanf("%d%s", &n, s);
   ll x = 1, ans = 1;
   while (x < n && s[x] == s[x - 1])
       x++, (ans *= 2) %= mod;
   printf("%lld\n", ans);
}
int main()
{
   scanf("%d", &T);
   while (T--)
   {
       solve();
   }
}

1006. I love sequences

待补。。

1008. I love exam

待补。。

1010. I love permutation

题意

给定 \(a\)\(p\),生成序列 \(\{b_i\} = a*i \% p\),求逆序对数量的奇偶性

分析

令这个排列为 \(\pi\),排列的第 \(i\) 个数为 \(\pi(i)\),排列的逆序对数为 \(n(\pi)\)\(\operatorname{sgn}(\pi)=(-1)^{n(\pi)}\)
\[\operatorname{sgn}(\pi)=\frac{\prod_{0<j<i \leq p-1} \pi(i)-\pi(j)}{\prod_{0<j<i \leq p-1} i-j}=\prod_{0<j<i \leq p-1} \frac{\pi(i)-\pi(j)}{i-j} \equiv \prod_{0<j<i \leq p-1} \frac{i a-j a}{i-j}=a^{\frac{P(P-1)}{2}} \equiv a^{\frac{P-1}{2}}(\bmod P)\]
于是直接计算 \(a^{\frac{p-1}{2}}(\bmod P)\) 的值, 就能知道 \(\operatorname{sgn}(\pi)\) 的值, 进而算出 \(n(\pi)\) 的奇偶性。

总结

考场队友罚坐 2h+,赛后看题解,果然是不会的东西.jpg 这题常规快速幂过不去,\(p\) 太大了,大数乘积取模 T 飞了,最后看 std 用 long double 过渡一下,就过了。。。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
int T = 1;
ll mul(ll a, ll b, ll k)
{
   ll tmp = (a * b - (ll)((long double)a / k * b + 1.0e-8) * k);
   return (tmp + k) % k;
}
ll ksm(ll a, ll b, ll k)
{
   if (!b)
       return 1 % k;
   a %= k;
   ll ret = 1;
   while (b)
   {
       if (b & 1)
           ret = mul(a, ret, k);
       a = mul(a, a, k);
       b >>= 1;
   }
   return ret;
}
void solve()
{
   ll a, p;
   scanf("%lld %lld", &a, &p);
   ll b = ksm(a, (p - 1) / 2, p);
   if (b == 1)
       puts("0");
   else
       puts("1");
}
int main()
{
   scanf("%d", &T);
   while (T--)
   {
       solve();
   }
}

1011. I love max and multiply

题意

给定序列 \(A_i,B_i\),求序列 \(C_k = Max(A_iB_j),(i\&j \ge k)\) 的和

分析

我们考虑枚举下标 \(i\),这个位置上的数字可以对 \(1~i\) 区间产生贡献。考虑正负,分类讨论即可。

总结

考场 debug 了 2h,最后发现是 inf 初始化小了。。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = (1 << 18) + 7, mod = 998244353;
const ll inf = 1e20;

int T = 1;
ll n, a[N], b[N], c[N];
struct node
{
   ll mxaz, mxbz, mxaf, mxbf, miaz, mibz, miaf, mibf;
} p[N];
void solve()
{
   scanf("%lld", &n);
   for (int i = 0; i < n; i++)
       scanf("%lld", &a[i]);
   for (int i = 0; i < n; i++)
       scanf("%lld", &b[i]);
   for (int i = 0; i < n; i++)
   {
       c[i] = -inf;
       if (a[i] >= 0)
       {
           p[i].mxaz = a[i];
           p[i].miaz = a[i];
           p[i].mxaf = 1;
           p[i].miaf = -inf;
       }
       else
       {
           p[i].mxaz = -1;
           p[i].miaz = inf;
           p[i].mxaf = a[i];
           p[i].miaf = a[i];
       }
   }
   for (int i = 0; i < n; i++)
   {
       if (b[i] >= 0)
       {
           p[i].mxbz = b[i];
           p[i].mibz = b[i];
           p[i].mxbf = 1;
           p[i].mibf = -inf;
       }
       else
       {
           p[i].mxbz = -1;
           p[i].mibz = inf;
           p[i].mxbf = b[i];
           p[i].mibf = b[i];
       }
   }
   int cnt = 0, nn = n;
   while (nn)
   {
       cnt++;
       nn /= 2;
   }
   for (int i = n - 1; i > -1; i--)
   {
       for (int j = 0; j < cnt; j++)
       {
           int t = i | (1 << j);
           if (t >= n)
               break;
           p[i].mxaz = max(p[i].mxaz, p[t].mxaz);
           p[i].mxbz = max(p[i].mxbz, p[t].mxbz);
           p[i].mxaf = min(p[i].mxaf, p[t].mxaf);
           p[i].mxbf = min(p[i].mxbf, p[t].mxbf);
           p[i].miaz = min(p[i].miaz, p[t].miaz);
           p[i].mibz = min(p[i].mibz, p[t].mibz);
           p[i].miaf = max(p[i].miaf, p[t].miaf);
           p[i].mibf = max(p[i].mibf, p[t].mibf);
       }
   }
   for (int i = 0; i < n; i++)
   {
       if (p[i].mxaz != -1 && p[i].mxbz != -1)
           c[i] = max(c[i], p[i].mxaz * p[i].mxbz);
       if (p[i].miaz != inf && p[i].mibf != -inf)
           c[i] = max(c[i], p[i].miaz * p[i].mibf);
       if (p[i].miaf != -inf && p[i].mibz != inf)
           c[i] = max(c[i], p[i].miaf * p[i].mibz);
       if (p[i].mxaf != 1 && p[i].mxbf != 1)
           c[i] = max(c[i], p[i].mxaf * p[i].mxbf);
   }
   ll ans = c[n - 1];
   for (int i = n - 2; i > -1; i--)
   {
       c[i] = max(c[i], c[i + 1]);
       ans += c[i] % mod + mod;
       ans %= mod;
   }

   printf("%lld\n", ans);
}
int main()
{
   scanf("%d", &T);
   while (T--)
   {
       solve();
   }
}

间歇性踌躇满志,持续性混吃等死