暑假集训2
LCIS
首先我赛时打了个\(n ^ {4}\)的暴力，因为一个转移的地方忘记加max了，然后拿了\(70\),本来以为改改也就T了结果它加了个\(max\)就\(A\)了.....这数据也是没谁了
暴力
#include <bits/stdc++.h>
#define int long long
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x ++)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define pr pair<int , int >
#define mk(x, y) makr_pair(x, y)
using namespace std;
namespace kiritokazuto{
auto read = [](){
LL x = 0;
int f = 1;
char c;
while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
return x * f;
};
template <typename T> fuc(void, write)(T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10); putchar(x % 10 | '0');
}
}
/*
咖啡不断加加加
加到厌倦
*/
using namespace kiritokazuto;
const int maxn = 3e4 + 100, Inf = 2147483647;
/*
虽然一看就知道是DP
可是咋又要推柿子
一个普遍适用的定义柿
dp[i][j]第一个串在第i位，第二个串在第j位
表示1 ~ i和1 ~ j中以i和j结尾最长公共上升子序列
然鹅很明显有一个n ^ 2暴力
啊呸, n ^ 4?????
我靠，我tm看成子序列了...
*/
int wmxa[maxn], wmxb[maxn];
int n;
int dp[4010][4010];
int ans = -0x7fffffffffffffff;
fuc(LL, maxx)(LL x, LL y){ return (x > y) ? x : y; }
//咱只求n ^ 4能多拿点分！
signed main(){
frein(lc);
freout(lc);
n = read();
fr(i, 1, n)wmxa[i] = read();
fr(i, 1, n) wmxb[i] = read();
fr(i, 1, n){
fr(j, 1, n){
if (wmxa[i] == wmxb[j]){
dp[i][j] = 1;
// 这个不加，因为我求的是区间
//rnm区间好难写，还是写终止吧
fr(l, 1, i){
fr(r, 1, j){
if (wmxa[l] == wmxb[r] && wmxa[i] > wmxa[l]){
// dp[i][j] = 1;
dp[i][j] = maxx(dp[i][j], dp[l][r] + 1ll);
// printf("dp[%d][%d] == %d dp[%d][%d] == %d\n", l, r, dp[l][r], i, j, dp[i][j]);
}
else if (wmxa[l] == wmxb[r] && wmxa[i] == wmxa[l] && wmxb[j] == wmxb[r]){
dp[i][j] = maxx(dp[i][j], dp[l][r]);
}
else{
dp[i][j] = maxx(1, dp[i][j]);
}
ans = maxx(ans, dp[i][j]);
}
}
}
}
}
// ki;
// fr(i, 1, n){
// fr(j, 1, n){
// printf("dp[%d][%d] == %d\n", i, j, dp[i][j]);
// }
// }
write(ans);
return 0;
}
/*
7
2 3 7 7 8 9 5
7 8 9 1 1 1 1
*/
然后是\(n ^ {2}\)并且压维的正解(wy还说他研究出\(O(n)\)的....(想多了)， 虽然这个\(n ^ {2}\)是他的)
- \(dp[i][j]\)表示序列\(a\)前\(i\)个数(不一定以i为结尾)序列\(b\)中以\(j\)为结尾的最长LCIS(限制一个结尾是为了保证上升，限制\(a\)也行)
- 首先来\(n ^ {3}\)的,如果\(a[i] != b[j]\)直接跳,否则就去找一个 \(k\in[1, j - 1]\)中\(dp[i - 1][k]\)最大的，同时\(b[k] < b[j]\)的来加一转移
- 优化成\(n ^ {2}\)的就是在第二层里一直维护一个\(Max\)就行
- 最后因为只和\(i\), \(i - 1\)有关系，可以压掉一维
wy
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int mx=3100+100;
const int Inf=0x7fffffff;
ll f[mx],a[mx],b[mx],n;
void MYH(){
scanf("%lld",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;++i){
scanf("%lld",&b[i]);
}
for(int i=1;i<=n;++i){
ll Max=0;
for(int j=1;j<=n;++j){
f[j]=f[j];
if(a[i]>b[j])Max=max(Max,f[j]);
if(a[i]==b[j])f[j]=Max+1;
}
}
ll ans=0;
for(int i=1;i<=n;++i){
ans=max(ans,f[i]);
}
printf("%lld\n",ans);
}
int main(){
freopen("lc.in","r",stdin);
freopen("lc.out","w",stdout);
MYH();
return 0;
}
平凡的函数
其实就是个改一改的欧拉筛，(我赛时都能切的大水题)
- 因为\(f(p ^ {c}) = p \oplus c\) (\(p\)为质数)所以相当于所有质数的\(f\)都已知了,又因为要通过质数筛出所有数，自然就想到了线性筛，因为有指数，又想到了唯一分解定理...然后就自然写出来了
here
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x ++)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<int , int >
#define mk(x, y) makr_pair(x, y)
using namespace std;
namespace kiritokazuto{
auto read = [](){
LL x = 0;
int f = 1;
char c;
while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
return x * f;
};
template <typename T> fuc(void, write)(T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10); putchar(x % 10 | '0');
}
}
/*
普通的disco我们普通地摇
旁边普通的路人在普通地尖叫
*/
/*
dp[1] = 1;
dp[p ^ c] = p ^ c
那么p或者c等于1的时候不就有了
这玩意怎么感觉像推啊？？？？
啊呸
没看到素数...
那么他俩互质
他俩因子也互质呗
...那我筛出素数来直接乘不就完了？？
《唯一分解定理》
*/
using namespace kiritokazuto;
const int maxn = 5e7 + 10;//能开下？？
//刚才想到了之前最小质因数那个题，感觉可以用，但是感觉晒不出来啊..
//试试吧
//tnnd没有l
int isprime[maxn];
LL prime[maxn], cnt = 0;
LL wmx[maxn];
//虽然但是，这玩意能过样例？？？？
//但是为啥它会停一下啊
//T飞吧？？？
//话说他为啥一个标准IO一个文件IO??
LL ans = 0;
fuc(LL, qpow)(LL x, LL y){//为啥这个题连个模数都不给..
LL res = 1;
while (y){
if (y & 1)res = (res * x);
x = (x * x);
y >>= 1;
}
return res;
}
fuc(void, getprime)(int x){
memset(isprime, 1, sizeof(isprime));
isprime[1] = 0;
fr(i, 2, x){
if (isprime[i]){
prime[++cnt] = i;
wmx[i] = i ^ 1;//素数直接搞
}
for (Re j = 1; j <= cnt && i * prime[j] <= x; j++){
isprime[i * prime[j]] = 0;
wmx[i * prime[j]] = wmx[prime[j]] * wmx[i];//i和prime[j]互质
if (i % prime[j] == 0){
LL tmp = i * prime[j];
int cot = 0;
LL tot = 1;
while (tmp % prime[j] == 0){
tmp /= prime[j];
cot++;
// tot = tot * prime[j];
}
tot = qpow(prime[j], cot);
wmx[tot] = prime[j] ^ cot;
if (tmp != 1){
wmx[i * prime[j]] = wmx[tot] * wmx[tmp];
}
break;
}
}
ans += wmx[i];
}
}
int n;
//话说我打表？？？？？？？？
/*
ri
控制不住想打表的冲动了
50000跑
3904.00000000ms
已经不行了
*/
/*
e..好像我判断条件和筛的时候一样
em...改了改
好像快了
拍了一会
好像没问题
*/
signed main(){
frein(func);
freout(func);
wmx[1] = 1;
// LD st = clock();
n = read();
getprime(n);
// fr(i, 1, cnt){
// write(prime[i]);
// fk;
// }
// fr(i, 1, n){
// if (isprime[i])continue;
// fr(j, 1, cnt){
// if (i % prime[j] == 0){
// int cot = 0;
// LL tmp = 0;
// int ii = i;
// while (ii % prime[j] == 0){
// ii /= prime[j];
// cot++;
// // tmp = tmp * prime[j];
// }
// tmp = qpow(prime[j], cot);
// wmx[tmp] = prime[j] ^ cot;
// if (ii){
// wmx[i] = wmx[ii] * wmx[tmp];
// //ii此时已经有值了
// }
// else{
// break;
// }
// }
// }
// }
// fr(i, 1, n){
// ans += wmx[i];
// }
write(ans + 1);
// ki;
// LD ed = clock();
// printf("%.8lf ", ed - st);
return 0;
}
那一天她离我而去
正解是分层最短路，因为出\(1\)和回\(1\)的点的二进制位至少有一位不同，所以他俩至少被分在不同组一次...然后就瞎搞呗
std
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x ++)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<int , int >
#define mk(x, y) makr_pair(x, y)
using namespace std;
namespace kiritokazuto{
auto read = [](){
LL x = 0;
int f = 1;
char c;
while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
return x * f;
};
template <typename T> fuc(void, write)(T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10); putchar(x % 10 | '0');
}
}
/*
梦里海市云霞
梦外羽化成她
水中月镜中花
*/
/*
悄悄看了一眼T4
md
不可做
看到期望就发怵
*/
using namespace kiritokazuto;
int t;
int n, m;
const int maxn = 2e5 + 100, Inf = 20000000;//这玩意爆int
struct Node{
int to, next, dis;
}wmx[maxn << 1];
//这不是昨天的二维dij吗？
//不建反图直接判？
//呃呃呃其实感觉王一昨天的枚举更diao来着
//内存好小啊
//还是枚举吧
//二维开不下
int head[maxn], len = 0;
int Head[maxn];
fuc(void, Qian)(int from, int to, int dis){
wmx[++len].to = to;
wmx[len].next = head[from];
wmx[len].dis = dis;
head[from] = len;
}
int dis[maxn];
int ans;
deque <int> q;
random_device seed;
mt19937 rrand(seed());
//我把和1相连的全砍一遍
//强行更改最短路
/*
日
调了半天
记住是记住了成对变换从零开始
就是习惯打1.............
*/
int vis[maxn];
fuc(void, Spfa) (int x){
mes(vis, 0);
mes(dis, 0x3f);
q.push_front(x);
vis[1] = 1;
dis[x] = 0;
while (!q.empty()){
int top = q.front();
q.pop_front();
vis[top] = 0;
for (Re i = head[top]; i; i = wmx[i].next){
int to = wmx[i].to;
int diss = wmx[i].dis;
// if (diss == -Inf){
// // pRef("KKKKKKKKKK to = %d\n", to);
// continue;
// }
if (dis[to] > dis[top] + diss){
dis[to] = dis[top] + diss;
if (vis[to])continue;
// q.push_back(to);
if (rrand() & 1)q.push_back(to);
else q.push_front(to);
vis[to] = 1;
// vis[to] = 1;
}
}
}
return;
}
fuc(void, init)(){
ans = INT_MAX;
len = 0;
// fr(i, 1, n)vis[i] = 0;
// mes(dis, 33);
//5558192971
mes(head, 0);
}
signed main(){
frein(leave);
freout(leave);
t = read();
while (t--){
init();
n = read();
m = read();
fr(i, 1, m){
int x = read(), y = read(), z = read();
Qian(x, y, z);Qian(y, x, z);
}
for (Re i = head[1];i;i = wmx[i].next) Head[wmx[i].to] = head[wmx[i].to];
Re now = len;
for (Re i = 0;n >> i;++i){
len = now;
for (Re j = head[1];j;j = wmx[j].next){
Re to = wmx[j].to;
if (to & (1 << i)) Qian(n + 1, to, wmx[j].dis);
else Qian(to, n + 2, wmx[j].dis);
}
Spfa(n + 1);
ans = min(ans, dis[n + 2]);
for (Re j = head[1];j;j = wmx[j].next) head[wmx[j].to] = Head[wmx[j].to];
head[n + 1] = head[n + 2] = 0;
}
write((ans == 0x3f3f3f3f) ? -1 : ans);
ki;
}
return 0;
}
我糊了一个暴力的做法，就是把和一相邻的点都断一次，然后从它跑到一，最后再加上它和一的边，每次取一下\(min\)
暴力
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x ++)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<int , int >
#define mk(x, y) makr_pair(x, y)
using namespace std;
namespace kiritokazuto{
auto read = [](){
LL x = 0;
int f = 1;
char c;
while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
return x * f;
};
template <typename T> fuc(void, write)(T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10); putchar(x % 10 | '0');
}
}
/*
梦里海市云霞
梦外羽化成她
水中月镜中花
*/
/*
悄悄看了一眼T4
md
不可做
看到期望就发怵
*/
using namespace kiritokazuto;
int t;
int n, m;
const int maxn = 2e5 + 100, Inf = 20000000;//这玩意爆int
struct Node{
int to, next, dis;
}wmx[maxn << 1];
//这不是昨天的二维dij吗？
//不建反图直接判？
//呃呃呃其实感觉王一昨天的枚举更diao来着
//内存好小啊
//还是枚举吧
//二维开不下
int head[maxn], len = 0;
fuc(void, Qian)(int from, int to, int dis){
wmx[len].to = to;
wmx[len].next = head[from];
wmx[len].dis = dis;
head[from] = len;
len++;
}
int dis[maxn];
int ans;
deque <int> q;
random_device seed;
mt19937 rrand(seed());
//我把和1相连的全砍一遍
//强行更改最短路
/*
日
调了半天
记住是记住了成对变换从零开始
就是习惯打1.............
*/
int vis[maxn];
fuc(void, Spfa) (int x){
fr(i, 1, n)vis[i] = 0;
mes(dis, 33);
q.push_front(x);
vis[x] = 1;
dis[x] = 0;
while (!q.empty()){
int top = q.front();
q.pop_front();
vis[top] = 0;
for (Re i = head[top]; i; i = wmx[i].next){
int to = wmx[i].to;
int diss = wmx[i].dis;
if (diss == -Inf){
// printf("KKKKKKKKKK to = %d\n", to);
continue;
}
if (dis[to] > dis[top] + diss){
dis[to] = dis[top] + diss;
if (vis[to])continue;
// q.push_back(to);
if (rrand() & 1)q.push_back(to);
else q.push_front(to);
vis[to] = 1;
// vis[to] = 1;
}
}
}
return;
}
fuc(void, init)(){
ans = Inf;
len = 0;
// fr(i, 1, n)vis[i] = 0;
// mes(dis, 33);
//5558192971
mes(head, 0);
}
signed main(){
frein(leave);
freout(leave);
t = read();
while (t--){
n = read();
m = read();
init();
// write(dis[1]);
fr(i, 1, m){
int x = read(), y = read(), z = read();
Qian(x, y, z);
Qian(y, x, z);
}
for (Re i = head[1]; i; i = wmx[i].next){
int tmp = wmx[i].dis;
int to = wmx[i].to;
wmx[i].dis = wmx[i ^ 1].dis = -Inf;
Spfa(to);
ans = min(ans, dis[1] + tmp);
// printf("to == %d \n", to);
// fr(k, 1, n){
// printf("dis[%d] = %d \n", k, dis[k]);
// }
// ki;
wmx[i].dis = wmx[i ^ 1].dis = tmp;
}
write((ans == Inf) ? -1 : ans);
ki;
}
return 0;
}
熟练剖分
呃，还不太懂，先咕掉
std
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x ++)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<int , int >
#define mk(x, y) makr_pair(x, y)
using namespace std;
namespace kiritokazuto{
auto read = [](){
LL x = 0;
int f = 1;
char c;
while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
return x * f;
};
template <typename T> fuc(void, write)(T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10); putchar(x % 10 | '0');
}
}
/*
*/
using namespace kiritokazuto;
const int maxn = 3e3 + 10, Mod = 1e9 + 7;
const int Inf = 2147483647;
int rt, fa[maxn], sz[maxn];
LL ans, dp[maxn][maxn], g[maxn], h[maxn];
int n;
struct Node{
int next, to;
}wmx[maxn << 1];
int head[maxn], len = 0;
fuc(void, Qian)(int from, int to){
wmx[++len].to = to;
wmx[len].next = head[from];
head[from] = len;
}
fuc(LL, qpow)(LL x, LL y){
LL res = 1;
while (y){
if (y & 1)res = (res * x) % Mod;
x = (x * x) % Mod;
y >>= 1;
}
return res % Mod;
}
fuc(void, dfs)(int x){
sz[x] = 1;
int cnt = 0;
for (Re i = head[x]; i; i = wmx[i].next){
int to = wmx[i].to;
cnt++;
dfs(to);
sz[x] += sz[to];
}
int tot = qpow(cnt, Mod - 2);
for (Re son = head[x]; son; son = wmx[son].next){
fr(j, 0, n) g[j] = 1;
for (Re st = head[x];st; st = wmx[st].next){
fr(k, 0, sz[wmx[st].to] + 1){
LL gk = g[k];
if (k) gk -= g[k - 1];
if (wmx[son].to == wmx[st].to){
LL fkg = dp[wmx[st].to][k];// dp[v][k]单点值
if (k) fkg -= dp[wmx[st].to][k - 1];
h[k] = (fkg * g[k] % Mod + dp[wmx[st].to][k] * gk % Mod - fkg * gk % Mod + Mod) % Mod;
}
else{
LL fk1 = dp[wmx[st].to][k - 1]; // dp[v][k-1]单点值
if (k > 1) fk1 -= dp[wmx[st].to][k - 2];
h[k] = (fk1 * g[k] % Mod + dp[wmx[st].to][k - 1] * gk % Mod - fk1 * gk % Mod + Mod) % Mod;
// u-v为轻边，到u为k即到v为k-1
}
}
g[0] = h[0], h[0] = 0;
fr(k, 1, sz[wmx[st].to] + 1) g[k] = (g[k - 1] + h[k]) % Mod, h[k] = 0;
}
for (Re j = sz[x]; j; --j) g[j] = (g[j] - g[j - 1] + Mod) % Mod;
fr(j, 0, sz[x]) dp[x][j] = (dp[x][j] + g[j] * tot) % Mod;
}
if (!cnt) dp[x][0] = 1;
fr(i, 1, sz[x] + 1) dp[x][i] = (dp[x][i] + dp[x][i - 1]) % Mod; // dp[u][i]为<=i的
}
signed main(){
frein(tree);
freout(tree);
n = read();
fr(i, 1, n){
int x = read();
fr(j, 1, x){
int y = read();
fa[y] = i;
Qian(i, y);
}
}
fr(i, 1, n){
if (!fa[i]){
rt = i;
break;
}
}
dfs(rt);
fr(i, 1, n){
ans = (ans + i * (dp[rt][i] - dp[rt][i - 1] + Mod) % Mod) % Mod;
}
write(ans);
return 0;
}
下边是e...教练的题解
A. 简单的函数弱化版
直接线性筛即可，需要用辅助数组记录最小质因子的次幂数。
B. 那一天她离我而去
一个暴力的思路是，将所有与起点相连的边删除，从这些相连的点跑到其他相连点的最短路尝试更新答案。
可以尝试优化这个暴力思路。
发现这个算法有一部分冗余，我们可以分组进行最短路。
因为任意两个不同的点，二进制一定至少存在一位不同。
我们以每个二进制位的0，1进行分组，每组点组成的环一定被至少一次更新，于是可以达到目的。
复杂度 \(O(m log^2n)\)
请不要写 spfa，虽然测试数据中没有卡。
标签：fr,LCIS,int,wmx,暑假,dis,集训,dp,define From： https://www.cnblogs.com/kiritokazuto/p/16596982.htmlC. 熟练剖分(tree)
容易发现总方案数为所有节点的儿子个数的乘积。
可以计算每个时间代价的方案数是多少，最后算出总答案，除掉总方案数就是期望。
这个东西可以通过 dp 来计算，设 \(dp_{i,j}\) 表示节点 \(i\) 子树中最坏时间代价为 \(j\) 的方案数。
在归并子树的过程中，给 dp 数组多加一维，表示是否已经选择过重儿子即可。