\(Preface\)
试验一下难度。———Au爷沈队(学长)
这句话，我理解为“铈囐镒䪗䁪鑟”。
\(Rank24/43\)
\(80pts + 9pts + 0pts +0pts = 89pts\)
\(\mathfrak{T1}\ 玩水\)
这个是场切题，找找规律就好了。
设这样一个点是“美丽点”：
x y
y z
\(x\)即为我所说的“美丽点”。
这只是我给他起了个名字((
考虑这个点的实际意义。这意味着在\(x\)位置有一个人可以和大部队分开，然后再在\(z\)点集合，这样就导致有一个人的路线和大部队的路线不相同，而走过的字符串是相同的。
那么找到两个这样的美丽点就行，这样\(3\)个人的路线就都不相同了。
但是会发现有不合法的情况出现。
由于题目限制只能往下或者往右走，所以当这种情况发生是不合法的：
x y b d
y z d h
e f
f g
可以看到\(x、b、e\)都是美丽点。但是从\(x\)点走到\(z\)点，就去不了\(b\)点或者\(e\)点了；从\(e\)点走到\(g\)点，也就去不了\(x\)点和\(b\)点了；从\(b\)点走到\(h\)点同理，也就去不了\(x\)点或\(e\)点了。
因此这样是不合法的。即\(x\)或\(y\)坐标相同的美丽点不能同时作为答案(特殊情况除外 (特殊情况就是这个下面我要说的这个\(↓\)) )
还有一种特殊的合法情况：
x y b
y b c
可以看到坐标为\((1, 1)、(1, 2)\)的两个点都是美丽点。我们显然一个人从\(x\)分开走下边的\(y\)，大部队走到上面的\(y\)后再让一个人分开走下边的\(b\)，最终三人在\(c\)点回合，发现字符串仍然是相同的，并且方案满足不同。
竖着的话同理。
也就是说，对于一个美丽点\((x, y)\)，除了点\((x+1, y)、(x, y+1)\)之外，其他\(x\)坐标或\(y\)坐标与\((x, y)\)相同的美丽点都不能同时作为答案。
其他的，也就是\(x、y\)坐标均与\((x, y)\)不相同的，设其坐标为\((a, b)\)，那么\((a, b)\)与\((x, y)\)能够同时作为答案当且仅当\((a, b)\)在\((x, y)\)的右下方。或者\((x, y)\)在\((a, b)\)的右下方。注意是严格的右下方。
至此本题就基本做完了。代码实现也很简单。
T1
// 删掉了一些调试信息以免引起各位的极度不适
#include <iostream>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 1005
#define CASE 12
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
好一个传纸条dp
爆搜是吗
我瞎搞直接输出草
n = 2的数据好弄，那个小性质直接搞一下输出就行？
其他的，我试试
只能向下或者向右走
好
对于一个右-下点 (i, j)，(i+2, j)、(i, j+2)都不能作为另一个【正确的】点
其他的都可以
那么对于右-下点们进行排序
首先满足x升序
再满足y升序
然后直接大力分类讨论
最坏情况下时间复杂度:O(n^4)
草
不对似乎并不是如此
可以O(n^2)预处理分一下块
直接开二维数组存不就行了
特殊判断一下点(n, m)
似乎涉及到
二维线段树?
我不会二维线段树
所以我写个假的二维线段树
浅算了一下完全能开的下
好
O(n^3 logn)大概
超！
然而并不知道这个理论是否正确
所以大概率会寄掉
我维护个粑粑的线段树
我就n^4枚举咋地
也不知道能不能行
超！
*/
bool final_ans;
int T, n, m, cnt;
char s[N][N];
struct Down_Right{int x, y;}a[N*N];
inline void Clean(){
final_ans = false; cnt = 0;
}
void work(){
Clean();
cin >> n >> m;
for (re i = 1 ; i <= n ; ++ i)
cin >> s[i]+1;
for (re i = 1 ; i <= n ; ++ i)
for (re j = 1 ; j <= m ; ++ j)
if (s[i][j+1] == s[i+1][j] and (i != n and j != m))
a[++ cnt].x=i, a[cnt].y=j;
for (re i = 1 ; i <= cnt ; ++ i){
for (re j = i+1 ; j <= cnt ; ++ j){
// 在同一行
if (a[i].x == a[j].x){
if (a[j].y == a[i].y+1)
{final_ans = true; goto Breaker;}
}
// 在同一列
else if (a[i].y == a[j].y){
if (a[j].x == a[i].x+1)
{final_ans = true; goto Breaker;}
}
// x、y都不相同
else
{final_ans = true; goto Breaker;}
}
}
Breaker:{}
cout << final_ans << '\n';
}
#define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(water);
#endif
Fastio_setup();
cin >> T;
while (T --)
work();
return GMY;
}
\(\mathfrak{T2}\ AVL树\)
我超！平衡树！跳跳跳...
这个题不会。。我连\(splay\)都没学。。
虽然考的并不是平衡树但是
并不妨碍我骗分。
除了根节点输出\(1\)之外，别的都输出\(0\)，可以获得\(9pts\)的好成绩。
代码不挂了，丢人。。。
\(\mathfrak{T3}\ 暴雨\)
我想喷一下出题人的语文水平。。。
浅问了一下，赛时大家基本都没读懂题。。
这题目描述就是个\(barbar\) ———\(CDsidi\)
这第二段就是个\(barbar\) ———\(CDsidi\)
第二段确实描述的令人难以理解，这让我想起了《生活在树上》
他其实叨叨了半天就是正常的积水，只不过两边(边界)没有积水而已(可以认为是边界再往外是平地)。
其实是个神仙题，我不会，我贺题解
T3
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 25002
#define P 1000000007
#define KKK 26
#define mod %
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
神仙题
思考无果
贺题解
*/
/*
7 1
2 5 2 4 1 6 2
*/
int n, K, final_ans;
int h[N], id[N];
struct Dynamic_Programming{
int a[N], cnt[N]; int val[N][KKK]; int dp[N][KKK][KKK][3];
multiset<int> s; map<int, int> mp[N];
multiset<int>::iterator it;
void prew(){
s.insert(0);
for (re i = 1 ; i <= n ; ++ i){
s.insert(a[i]), it = s.end();
for (re j = 1 ; j <= K+1 ; ++ j){
if (it == s.begin())
break;
it = prev(it), mp[i][*it] = ++ cnt[i], val[i][cnt[i]] = *it;
}
}
dp[0][1][0][0] = 1; cnt[0] = 1; val[0][1] = 0;
for (re i = 0 ; i <= n-1 ; ++ i){
for (re j = 1 ; j <= cnt[i] ; ++ j){
for (re k = 0 ; k <= K ; ++ k){
for (re p = 0 ; p <= 1 ; ++ p){
if (dp[i][j][k][p] == 0)
continue;
if (val[i][j] >= a[i+1]){
int nxj = mp[i+1][val[i][j]], nxp = p ^ ((val[i][j]-a[i+1]) & 1);
dp[i+1][nxj][k][nxp] = (dp[i+1][nxj][k][nxp] + dp[i][j][k][p]) mod P;
nxp = p ^ (val[i][j] & 1);
if (k+1 <= K)
dp[i+1][nxj][k+1][nxp] = (dp[i+1][nxj][k+1][nxp] + dp[i][j][k][p]) mod P;
}
else {
int nxj = mp[i+1][a[i+1]], nxp = p ^ (val[i][j] & 1);
dp[i+1][nxj][k][p] = (dp[i+1][nxj][k][p] + dp[i][j][k][p]) mod P;
nxj = mp[i+1][val[i][j]];
if (k+1 <= K)
dp[i+1][nxj][k+1][nxp] = (dp[i+1][nxj][k+1][nxp] + dp[i][j][k][p]) mod P;
}
}
}
}
}
}
}f, g;// 正 和 反
// Hikari and Taritsu (doge
inline bool comp(int i, int j){return h[i] > h[j];}
void work(){
cin >> n >> K;
for (re i = 1 ; i <= n ; ++ i)
{cin >> h[i]; id[i] = i, f.a[i] = g.a[n-i+1] = h[i];}
f.prew(), g.prew();
sort(id+1, id+n+1, comp);
for (re i = 1 ; i <= n ; ++ i){
if (h[id[i]] < h[id[K+1]])
break;
int x = id[i], w = h[id[i]];
for (re j = f.cnt[x-1] ; j >= 1 ; -- j){
if (f.val[x-1][j] > w)
break;
for (re k = g.cnt[n-x] ; k >= 1 ; -- k){
if (g.val[n-x][k] >= w)
break;
for (re d = 0 ; d <= K ; ++ d){
final_ans = (final_ans + (long long)f.dp[x-1][j][d][0] * g.dp[n-x][k][K-d][0] mod P) mod P;
final_ans = (final_ans + (long long)f.dp[x-1][j][d][1] * g.dp[n-x][k][K-d][1] mod P) mod P;
}
// cerr << final_ans << '\n';
}
}
}
/*for (re i = 1 ; i <= n ; ++ i)
cout << id[i] << '\n';*/
/*for (re i = 1 ; i <= n ; ++ i){
for (re j = 1 ; j <= K ; ++ j){
for (re k = 1 ; k <= K ; ++ k){
for (re p = 0 ; p <= 1 ; ++ p){
cout << g.dp[i][j][k][p] << _;
}
cout << '\n';
}
}
}*/
/*for (re i = 1 ; i <= n ; ++ i)
for (re k = 1 ; k <= K ; ++ k)
cout << f.val[i][k] << _ << g.val[i][k] << '\n';*/
/*cerr << n << _ << K;
for (re i = 1 ; i <= n ; ++ i)
cerr << h[i] << _;
cerr << '\n';*/
cout << final_ans << '\n';
}
#define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(rain);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T4}\ 置换\)
这题我也不会，连题解都没贺，但是难度比\(T3\)要小？
暴力是环长直接求个\(LCM\)，有\(10pts\)
T4·暴力10pts
#include <iostream>
#include <algorithm>
#include <cstring>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 205
#define mod %
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
int n, P, fz, fm, tpz, tpm;
char vis[N];
int a[N];
inline long long ksm(long long A, long long B){
long long res(1);
while (B != 0){
if ((B & 1) == 1) res = res * A mod P;
A = A * A mod P;
B >>= 1;
}
return res;
}
long long gcd(long long x, long long y){return ((y == 0) ? (x) : (gcd(y, x%y)));}
inline long long LCM(long long x, long long y){return (x * y / gcd(x, y));}
void work(){
cin >> n >> P;
for (re i = 1 ; i <= n ; ++ i)
a[i] = i;
fm = 1;
for (long long i = n ; i >= 2 ; -- i)
fm = fm * i mod P;
do{
tpz = 1; memset(vis, false, sizeof(vis));
for (re i = 1 ; i <= n ; ++ i){
if (vis[i] == true)
continue;
int x = i, num(0);
while (vis[x] == false)
vis[x] = true, x = a[x], num ++;
tpz = LCM(tpz, num);
}
tpz = tpz * tpz mod P;
fz = (fz + tpz) mod P;
}while (next_permutation(a+1, a+n+1));
// cerr << fz << _ << fm << '\n';
cout << fz * ksm(fm, P-2) mod P << endl;
}
#define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(perm);
#endif
Fastio_setup();
work();
return GMY;
}