E 弦
显然我们需要给出所有弦不交的概率P。
先对分子（两两相连且不相交的情况总数）进行推导：
其实这和经典题目凸多边形的三角形划分很相似（但我也没有做过）。
易知 时有1种情况,
有2种情况。
时有五种情况，如图：
其实这里已经可以大概猜到是卡特兰数了，但是这里我们做一些更严谨的推导，网上的推导要么就是没有，要么就复杂而且不讲人话。下面给出一种简洁的证法来证明连不相交弦的情况总数为卡特兰数。
众所周知，卡特兰数本身和栈/递归联系非常紧密。所以无论是理解还是证明卡特兰数，引入递归的思想十分重要。
比如对于n=4的情况，我们轻轻地连一条线。此时圆被我们切割成了两个部分：线的左边和右边。左边和右边都是同样的问题，也就是同质子问题。在这里，线的左边转换成了n=1的情况，线的右边转化成了n=2的情况。不断地分割，直到不可分割（n=0），也是递归的出口。
依次连接1-2,1-4,1-6,1-8，这四种情况就对应着四个分式：
所以数学归纳法推广到
即分子为卡特兰数。故分子满足
下面计算分母。
一开始在个点里随便选两个，然后在
个点里随便选两个……然后在最后剩下的两个点里面选2个，于是我们就得到了
。
但是！算重了！
以n=2举例
分别对应
1-2 3-4 1-3 2-4 1-4 2-3 2-3 1-4 2-4 1-3 3-4 1-2
可以发现算重了一遍，但去重并不是/=2
以n=3举例 ，第一轮重复数量/=1，第二轮重复数量/=2，第三轮重复数量/=3.
在上面的计算方式中，每次选取选了两个点确定了一条边，但是这n个边并没有定顺序，所以除以一个全排列
所以我们得到了下面的公式：
化简得到：
然后就很简单了，快速幂+费马小定理得逆元。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll qkpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll getInv(ll a) { return qkpow(a, mod - 2); } //求一个数的逆元
int main() {
ll n;
cin >> n;
ll ans = 1;
for (int i = 2; i <= n + 1; ++i) ans *= i, ans %= mod;
ans = qkpow(2, n) * getInv(ans) % mod;
cout << ans << endl;
return 0;
} F 排列计算
如果通过僵硬地涂色来计算单点权重，2e5*2e5必然TLE。
差分+前缀和可以完美地解决这个问腿。此处感谢钟涛大佬。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
ll num[N];
int main() {
ll n, m ;
cin >> n >> m;
while (m--) {
ll l , r ;
cin >> l >> r;
num[l]++;
num[r + 1]--;
}
for (int i = 2; i <= n; ++i) num[i] += num[i - 1];
sort(num + 1, num + 1 + n);
ll ans = 0;
for (int i = 1; i <= n; ++i) ans += i * num[i];
cout << ans << endl;
return 0;
} A 游戏
因为是两个人，而且最后一定会把能拿的数全部拿完。所以我们只需要讨论能拿的数sum有多少个即可。
- 如果a,b两个数不互质，即他们的最大公因数g大于1，那么在
范围内，所有满足的
的数都会被拿走。
- 如果a,b两个数互质，即他们的最大公因数g等于1，那么在
所以我们知道sum=n/gcd(a,b)，因为只有两人，且谁完成最后一次操作时，谁获胜。所以sum偶数时张老师必输，奇数时张老师必胜。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
inline ll read() {
ll s = 0, f = 1;
char ch;
do {
ch = getchar();
if (ch == '-') f = -1;
} while (ch < 48 || ch > 57);
while (ch >= 48 && ch <= 57)
s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
int main() {
ll t = read();
while (t--) {
ll n = read(), a = read(), b = read();
n /= __gcd(a, b);
if (n & 1) puts("Yes");
else puts("No");
}
return 0;
} B 伤害计算
水题，因为不想写字符串处理所以用py十行搞定：
s=list(input().split('+'))
ans=0.0
for i in s:
flag=0
for j in i:
if j=='d':
flag=1
break
if flag:
a,b=map(int,i.split('d'))
ans+=(1+b)*a*0.5
else:
ans+=int(i)
if ans-int(ans)>0.1:
print(ans)
else :
ans=int(ans)
print(ans) D 车辆调度
因为数据很小，我们都意识到了暴力搜索，DFS可以更简单地解决。
这题的主要难点在于编码难度，我在写这道题的时候认为每搜索一次重新开辟一个二维数组太蠢，又没想清楚如何动态管理车辆的位置信息，其实不需要管理车辆信息，每次重新搜索就可以了。
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
const int inf = 0x3f3f3f3f;
char mp[N][N];
int dx[] = {0, 0, -1, 1};//合起来分别对应上下左右
int dy[] = {1, -1, 0, 0};
int flag, n, m, k;
bool check(int x, int y) { //找合法位置，在区域内且不可遇到障碍物
return x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != 'R' &&
mp[x][y] != 'X';
}
void dfs(int cnt) {
if (cnt >= k) return;
if (flag) return;
for (int i = 1; i <= n; i++) //这样搜索就不用管理坐标了
for (int j = 1; j <= m; j++)
if (mp[i][j] == 'R') //枚举每一辆车
for (int k = 0; k < 4; k++) { //枚举每一个方向
int tx = i, ty = j;
while (check(tx + dx[k], ty + dy[k]))
tx += dx[k], ty += dy[k]; //不断向前
if (mp[tx][ty] == 'D') flag = 1; //如果抵达 设为完成
swap(mp[tx][ty], mp[i][j]); //换过去
dfs(cnt + 1); //向下搜索
swap(mp[tx][ty], mp[i][j]); //换回来
}
}
int main() {
cin >> m >> n >> k;
for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
dfs(0);
puts(flag ? "YES" : "NO");
return 0;
} 改了一下我比赛的时候写的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[15][15];
bool finish = 0;
int w, h, ti, a, b;
void turnright(int x, int y) {
int i;
for (i = y + 1; i <= w; ++i)
if (s[x][i] != '.' && s[x][i] != 'D') break;
if (s[x][i - 1] == 'D') finish = 1;
a = x, b = i - 1;
}
void turnleft(int x, int y) {
int i;
for (i = y - 1; i > 0; --i)
if (s[x][i] != '.' && s[x][i] != 'D') break;
if (s[x][i + 1] == 'D') finish = 1;
a = x, b = i + 1;
}
void turndown(int x, int y) {
int i;
for (i = x + 1; i <= h; ++i)
if (s[i][y] != '.' && s[i][y] != 'D') break;
if (s[i - 1][y] == 'D') finish = 1;
a = i - 1, b = y;
}
void turnup(int x, int y) {
int i;
for (i = x - 1; i; --i)
if (s[i][y] != '.' && s[i][y] != 'D') break;
if (s[i + 1][y] == 'D') finish = 1;
a = i + 1, b = y;
}
void dfs(int times) {
if (finish) return;
if (times > ti) return;
for (int i = 1; i <= h; ++i)
for (int j = 1; j <= w; ++j)
if (s[i][j] == 'R') {
int xi, yi;
turnup(i, j), swap(s[i][j], s[a][b]), xi = a, yi = b;
dfs(times + 1), swap(s[i][j], s[xi][yi]);
if (finish) return;
turndown(i, j), swap(s[i][j], s[a][b]), xi = a, yi = b;
dfs(times + 1), swap(s[i][j], s[xi][yi]);
if (finish) return;
turnleft(i, j), swap(s[i][j], s[a][b]), xi = a, yi = b;
dfs(times + 1), swap(s[i][j], s[xi][yi]);
if (finish) return;
turnright(i, j), swap(s[i][j], s[a][b]), xi = a, yi = b;
dfs(times + 1), swap(s[i][j], s[xi][yi]);
if (finish) return;
}
}
int main() {
scanf("%d%d%d", &w, &h, &ti);
for (int i = 1; i <= h; ++i) scanf("%s", s[i] + 1);
dfs(1);
puts(finish ? "YES" : "NO");
return 0;
} C 旅行
题意
n个点在数轴上排列，从其中一个点出发。每个点都有要求的最晚到达时间，问能否全部准时到达，如果能，给出完成时间。
分析
题目给出的n个景点是按照位置信息升序排列的。
把起始点，即t为0的点设为k，所有的点分成了两部分：k点左边的点和k点右边的点。
我们用一个数组dp[i][j][f]表示完成左边i个点右边j个点的最少所需时间，f==0时表示在左边结束，f==1时表示在右边结束。
看着数轴，考虑在左边结束的情况，即dp[i][j][0]：
- 上一个落脚点是左边（从右往左数，下同）第i-1个点，那么就是dp[i-1][j][0]再加上两点之间所需要消耗的时间即可。
- 上一个落脚点是右边第j个点.
所以
同理
然后逐个比对，遇到不符合的情况直接退出即可。
solution
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 5;
int dp[N][N][2];
int d[N], t[N];
int main() {
int n,k;
cin >> n;
for (int i = 1; i <= n; i++) cin >> d[i];
for (int i = 1; i <= n; i++) cin >> t[i];
for (int i = 1; i <= n; i++) if (t[i] == 0) k = i;
fill(**dp, **dp+sizeof(dp)/4, INF);
dp[0][0][1] = dp[0][0][0] = 0;
for (int i = 0; i <= k - 1; i++)
for (int j = 0; j <= n - k; j++) {
if (i) dp[i][j][0] = min(dp[i - 1][j][0] - d[k - i] + d[k - i + 1], dp[i - 1][j][1] + d[j + k] - d[k - i]);
if (j) dp[i][j][1] = min(dp[i][j - 1][1] + d[j + k] - d[j - 1 + k], dp[i][j - 1][0] + d[j + k] - d[k - i]);
if (dp[i][j][0] > t[k - i] && dp[i][j][1] > t[j + k]) { cout << -1; return 0; }
if (dp[i][j][0] > t[k - i]) dp[i][j][0] = INF;
if (dp[i][j][1] > t[k + j]) dp[i][j][1] = INF;
}
cout << min(dp[k - 1][n - k][0], dp[k - 1][n - k][1]);
return 0;
} 因为这是我第一次写区间DP，所以犯了很多沙雕错误。
- 区间DP的起始点是
for (int i = 0; i <= x; i++)这样的。 - 再比如这样的求最小，是把所有的不合法位置初始化为INF。
- 还有就是一些非常沙雕的越界了。
题目思路我就花了十几分钟……感谢刘晟大佬的帮助。
J 斐波那契和
给定n,k，求
比赛的时候找规律失败了
看不懂的官方题解，就算看懂了下次碰到还是不会
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod=998244353;
int k;
ll c[101][101];
struct ma
{
int m[203][203];
int n;
ma(int k)
{
n=2*k+3;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
m[i][j]=0;
}
ma operator*(const ma &a)
{
ma ans(k);
for(int i=0;i<n;i++)
for(int k=0;k<n;k++)
if(m[i][k]!=0)
for(int j=0;j<n;j++)
ans.m[i][j]=(ans.m[i][j]+1ll*m[i][k]*a.m[k][j]%mod)%mod;
return ans;
}
};
void init()
{
for(int i=0;i<101;i++)
c[i][0]=1;
for(int i=1;i<101;i++)
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
ma qpow(ma a,ll n)
{
ma ans(k);
for(int i=0;i<ans.n;i++)
ans.m[i][i]=1;
while(n)
{
if(n&1)
ans=ans*a;
n>>=1;
a=a*a;
}
return ans;
}
int main()
{
init();
ll n;
int nn;
cin>>n>>k;
nn=2*k+3;
if(n==1)
return puts("1"),0;
ma ans(k),mid(k);
ans.m[0][0]=mid.m[0][0]=1;
for(int i=1;i<nn;i++)
{
if(i&1)
ans.m[0][i]=1;
mid.m[i][0]=c[k][(i-1)/2];
}
for(int j=1;j<nn;j++)
for(int i=j;i<nn;i++)
{
if(j&1)
mid.m[i][j]=c[k-(j-1)/2][(nn-i-1)/2];
else if(i%2==0)
mid.m[i-1][j]=c[k-(j-1)/2][(nn-i-1)/2];
}
ans=ans*qpow(mid,n-1);
cout<<ans.m[0][0]<<endl;
return 0;
} 大概这就是出题人意图
然而这题可以用杜教筛板子
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
typedef long long ll;
#define SZ(x) ((ll)(x).size())
typedef vector<ll> VI;
typedef pair<ll, ll> PII;
const ll mod = 998244353;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % mod; a = a * a % mod; }return res; }
// head
ll _, n;
namespace linear_seq {
const ll N = 10010;
ll res[N], base[N], _c[N], _md[N];
vector<ll> Md;
void mul(ll* a, ll* b, ll k) {
rep(i, 0, k + k) _c[i] = 0;
rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] = (_c[i + j] + a[i] * b[j]) % mod;
for (ll i = k + k - 1; i >= k; i--) if (_c[i])
rep(j, 0, SZ(Md)) _c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
rep(i, 0, k) a[i] = _c[i];
}
ll solve(ll n, VI a, VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
// printf("%d\n",SZ(b));
ll ans = 0, pnt = 0;
ll k = SZ(a);
assert(SZ(a) == SZ(b));
rep(i, 0, k) _md[k - 1 - i] = -a[i]; _md[k] = 1;
Md.clear();
rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
rep(i, 0, k) res[i] = base[i] = 0;
res[0] = 1;
while ((1ll << pnt) <= n) pnt++;
for (ll p = pnt; p >= 0; p--) {
mul(res, res, k);
if ((n >> p) & 1) {
for (ll i = k - 1; i >= 0; i--) res[i + 1] = res[i]; res[0] = 0;
rep(j, 0, SZ(Md)) res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
}
}
rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
if (ans < 0) ans += mod;
return ans;
}
VI BM(VI s) {
VI C(1, 1), B(1, 1);
ll L = 0, m = 1, b = 1;
rep(n, 0, SZ(s)) {
ll d = 0;
rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;
if (d == 0) ++m;
else if (2 * L <= n) {
VI T = C;
ll c = mod - d * powmod(b, mod - 2) % mod;
while (SZ(C) < SZ(B) + m) C.pb(0);
rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
L = n + 1 - L; B = T; b = d; m = 1;
}
else {
ll c = mod - d * powmod(b, mod - 2) % mod;
while (SZ(C) < SZ(B) + m) C.pb(0);
rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
++m;
}
}
return C;
}
ll gao(VI a, ll n) {
VI c = BM(a);
c.erase(c.begin());
rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;
return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));
}
};
inline ll read() {
ll s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
ll f[10005];
int main() {
ll n = read(), k = read();
f[1] = 1, f[2] = 1;
for (int i = 3; i <= 10000; ++i)
f[i] = (f[i - 1] + f[i - 2]) % mod;
VI a;
ll x = 0;
for (int i = 1; i <= 10000; ++i) {
x = (x + powmod(i, k) * f[i] % mod) % mod;
a.push_back(x);
}
printf("%lld\n", linear_seq::gao(a, n - 1));
} #include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
typedef long long ll;
const int N = 2e5+5;
ll tree[N],a[N];
int n, m;
void add(int x, ll num) {
while (x <= n) {
tree[x] += num;
x += lowbit(x);
}
}
ll query(int x) {
ll ans = 0;
while (x) { ans += tree[x]; x -= lowbit(x); }
return ans;
}
int main(){
cin>>n>>m;
while (m--) {
int x, y;
cin>>x>>y;
add(x, 1);//差分处理
add(y + 1, -1);
}
for(int i=1;i<=n;i++)a[i]=query(i);
sort(a+1,a+1+n);
ll ans=0;
for(int i=1;i<=n;i++)ans+=a[i]*i;
cout<<ans;
return 0;
} 
京公网安备 11010502036488号