9573

#include <bits/stdc++.h>
using namespace std;
queue<int>q;
queue<int>p;

int main(){
int n , m , t ;
cin >> n >> m ;
while(n--){
cin >> t;
q.push(t);
}
while(m--){
cin >> t;
p.push(t);
}
while( !q.empty() && !p.empty() ){
if( q.front() == p.front())q.pop();
p.pop();
}
if( q.empty() )cout << "Yes";
else cout << "No";
}


#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false);\
cin.tie(0);\
cout.tie(0)
#define FI(x) fixed<<setprecision(x)<<
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n;
priority_queue<int> q;
ll sum = 0;
int main()
{
IO; // 加快cin和cout的速度(基本和scanf差不多)
cin >> n;
for(int i = 1; i <= n; i ++)
{
int x;
cin >> x;
q.push(x);
}
while(q.size() > 1)
{
int x = q.top();
q.pop();
int y = q.top();
q.pop();
q.push(x + y);
sum += 1ll * x * y;
}
cout << sum << '\n';
return 0;
}



### 按照五子棋连子的方向进行模拟检验即可

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n;
int g[N][N];

bool check(int x, int y, int val, int dx, int dy)
{
int cnt = 1;
int nx = x, ny = y;
while (true) {
nx += dx, ny += dy;
if (g[nx][ny] != val)
break;
else {
cnt ++;
}
}

nx = x, ny = y;
while (true) {
nx -= dx, ny -= dy;
if (g[nx][ny] != val)
break;
else {
cnt ++;
}
}
return cnt >= 5;
}

bool Check(int x, int y, int val)
{
// shang xia, zuoyou, zuoxie, youxie
if (check(x, y, val, 1, 0))
return true;
else if (check(x, y, val, 0, 1))
return true;
else if (check(x, y, val, 1, -1))
return true;
else if (check(x, y, val, 1, 1))
return true;
else
return false;
}

int main()
{
memset(g, -1, sizeof g);

bool flag = false;
cin >> n;
for (int i = 1; i <= n; i ++ ) {
static int x, y;
scanf("%d%d", &x, &y);
if (i & 1) {    // A ,, 0
g[x][y] = 0;
if (Check(x, y, 0)) {
cout << "A " << i << endl;
flag = true;
break;
}
}
else {  // B ,, 1
g[x][y] = 1;
if (Check(x, y, 1)) {
cout << "B " << i << endl;
flag = true;
break;
}
}
}

if (!flag)   cout << "Tie" << endl;

return 0;
}


### 一个比较简单的模拟题目

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
bool st[N];
int n;

int main()
{
cin >> n;
memset(st, false, sizeof st);
for (int i = 1; i <= n; i ++ ) {
static int x;
scanf("%d", &x);
st[x] = true;
}

int cur = 0;
while (true) {
if (st[cur] == false) {
cout << cur << endl;
break;
}
cur ++;
}

return 0;
}


/*

f[i][j] : 表示 区间 i -> j 完成匹配之后需要的最小操作次数

*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;
char a[N];
int f[N][N];
int n;

bool is_match(char a, char b)
{
if (a == '[' && b == ']')   return true;
else if(a == '(' && b == ')')   return true;
return false;
}

int main()
{
cin >> a;
n = strlen(a);

memset(f, 0, sizeof f);
for (int len = 1; len <= n; len ++ )
{
for (int i = 0; i + len - 1 < n; i ++ )
{
static int j;
j = i + len - 1;
f[i][j] = INF;
if (len != 1 && is_match(a[i], a[j]))
{
f[i][j] = min(f[i][j], f[i+1][j-1]);
}
else
{
f[i][j] = min(f[i][j], min(f[i+1][j], f[i][j-1]) + 1);
}

for (int k = i; k < j; k ++ )
{
f[i][j] = min(f[i][j], f[i][k] + f[k+1][j]);
}
}
}

cout << f[0][n-1] << endl;

return 0;
}



### 直接就是进行动态规划

/*
或许可以直接dp进行写，看看是否存在连续几个的
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int M = 101010, N = 110, INF = 0x3f3f3f3f;
int a[N];
int n;
bool st[M + 10];

bool Check(int x)
{
for (int i = 1; i <= n; i ++ )
{
if (x - a[i] >= 0 && st[x - a[i]])
{
return true;
}
}
return false;
}

int main()
{
cin >> n;
int mmin = INF;
memset(st, false, sizeof st);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
mmin = min(mmin, a[i]);
}
int cnt = mmin - 1, con = 0;
bool flag = false;

st[0] = true;
for (int i = mmin; i < M; i ++ )
{
// printf("I:%d\n", i);
if (Check(i))
{
st[i] = true;
con ++;
if (con >= mmin)
{
flag = true;
break;
}
}
else
{
st[i] = false;
con = 0;        // 注意这个是清0，不是 1
cnt ++;
// printf("%d\n", i);
}
}

if (flag)
{
printf("%d\n", cnt);
}
else
{
printf("INF\n");
}
return 0;
}



### 先进行gcd特判，然后动态规划，不过使用的是完全背包dp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010, M = 10010;
int a[110];
bool f[110][N];
int n;

// 求解最大公因数
int gcd(int a, int b)
{
if (b == 0) return a;
else    return  gcd(b, a % b);
}

int main()
{
int res = 0;

cin >> n;
for (int i = 1; i <= n; i ++ )  scanf("%d", &a[i]);

int d = a[1];
for (int i = 2; i <= n; i ++ )
{
d = gcd(d, a[i]);
}

if (d != 1)
{
printf("INF\n");        // 结果具有无穷多个
return 0;
}

// 直接进行完全背包问题进行求解
//  f[i][j] 使用前 i 个数字，能否凑出来 j
//  f[i][j] = f[i-1][j] | f[i-1][j-a[i]] | f[i-1][j-2a[i]] | f[i-1][j-3a[i]]...
//  f[i][j] = f[i-1][j] | f[i][j-a[i]]

memset(f, false, sizeof f);
f[0][0] = true;
for (int i = 1; i <= n; i ++ )
{
for (int j = 0; j < M; j ++ )
{
f[i][j] = f[i-1][j];
if (j >= a[i])  f[i][j] |= f[i][j-a[i]];
}
}

int cnt = 0;
for (int j = 0; j < M; j ++ )
{
if (!f[n][j])
{
cnt ++;
// printf("%d, ", j);
}
}

cout << cnt << endl;

return 0;
}


#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 3;
LL n, m;

void mul(LL *c, LL *a, LL b[][N])
{
static LL tmp[N];
memset(tmp, 0, sizeof tmp);

for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
tmp[i] = (tmp[i] + a[j] * b[j][i]) % m;
}
}

memcpy(c, tmp, sizeof tmp);       // 注意一定要使用tmp
}

void mul(LL c[][N], LL a[][N], LL b[][N])
{
static LL tmp[N][N];
memset(tmp, 0, sizeof tmp);

for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < N; k++)
{
tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % m;
}
}
}
memcpy(c, tmp, sizeof tmp);       // 注意一定要使用tmp
}

int main()
{
cin>>n>>m;

LL a[N][N] = {
{1LL, 0LL, 0LL},
{1LL, 1LL, 1LL},
{1LL, 1LL, 0LL},
};

LL f1[N] = {1, 1, 0};

n--;        // 需要进行n-1次
//
/*
for (int i = 1; i <= n; i ++ )
{
mul(f1, f1, a);
printf("I:%d; ", i + 1);
for (int j = 0; j < N; j ++ )
{
printf("%d ", f1[j]);
}
cout<<endl;
}
*/

while (n)
{
if (n & 1)
{
mul(f1, f1, a);
}
mul(a, a, a);
n >>= 1;
}

cout << f1[0] << endl;
return 0;
}

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 3;
LL n, m;

void mul(LL *c, LL *a, LL b[][N])
{
static LL tmp[N];
memset(tmp, 0, sizeof tmp);

for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
tmp[i] = (tmp[i] + a[j] * b[j][i]) % m;
}
}

memcpy(c, tmp, sizeof tmp);       // 注意一定要使用tmp
}

void mul(LL c[][N], LL a[][N], LL b[][N])
{
static LL tmp[N][N];
memset(tmp, 0, sizeof tmp);

for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < N; k++)
{
tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % m;
}
}
}
memcpy(c, tmp, sizeof tmp);       // 注意一定要使用tmp
}

int main()
{
cin>>n>>m;

LL a[N][N] = {
{2LL, 1LL, 0LL},
{0LL, 0LL, 1LL},
{-1LL, 0LL, 0LL},
};

LL f1[N] = {2, 1, 0};

n -= 2;        // 需要进行n-2次
/*
for (int i = 1; i <= n; i ++ )
{
mul(f1, f1, a);
printf("I:%d; ", i + 1);
for (int j = 0; j < N; j ++ )
{
printf("%d ", f1[j]);
}
cout<<endl;
}
*/

while (n)
{
if (n & 1)
{
mul(f1, f1, a);
}
mul(a, a, a);
n >>= 1;
}

cout << (f1[0] + m) % m << endl;
return 0;
}



/*

类似于dp树的直径，不过是把边权换成了点的权值
分析错误，这个更像是一个连通块的问题
连通块进行dp，往往需要进行按照 树形dp进行考虑， 也就是需要
f[i] 表示以i为根的连通块
而且因为树这个数据结构的特殊性，他的子树自己是相互独立的，更方便我们的dp的规划

f[i] 表示 以 i 为根的连通块的最大值
f[fa] = w[fa] + segment(f[son], 0);

*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 200010;
int h[N], e[N], ne[N], idx;
int w[N];
int n;
LL f[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa)
{
f[u] = w[u];
int v;
for (int i = h[u]; ~i; i = ne[i])
{
v = e[i];           // 注意，这里不可以进行static，因为这个是dfs，wc
if (v == fa)    continue;
dfs(v, u);
f[u] += max(0ll, f[v]);     // 注意这里需要加的 long long
}
}

int main()
{
// input
cin>>n;
for (int i = 1; i <= n; i ++ )  scanf("%d", &w[i]);
idx = 0;
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++ )
{
static int a, b;
scanf("%d%d", &a, &b);
}

// inital and dp
memset(f, 0, sizeof f);
dfs(1, -1);

// output
LL res = f[1];
for (int i = 2; i <= n; i ++ )
{
res = max(res, f[i]);
}
cout<<res<<endl;

return 0;
}



/*

进行 n 次数列的处理，然后使得 max(abs(a[i])) 尽可能的小

首先将原问题转换为 前缀和进行分析求解
swap(s[i-1], s[i]),  2 <= i <= n-1 (即为 1 ~ n-1 数组的数据是可以任意交换的)

问题也就是变成了 如何 调整 s1 - sn-1 让 s0 ~ (n-1个数字的数组) ~ sn 的 max abs差值最小

S0 --> Min --> Max --> Sn

也就是说 Min ~ S0
Sn ~ Max 需要拆开成两条路径使用，关键是如何进行拆，使得相邻的绝对值之差小

可以证明使用隔一个拆一下最好，而且为了方便代码的书写，我们直接使用st数组记录隔一个取一个的路径
之后直接使用按照st数组过一遍，就知道哪些没取，作为第二个路径

小心分析过程中的 LL 问题
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 300010;
LL a[N], s[N];
int n;
bool st[N];

int main()
{
int T;  cin>>T;
while (T--)
{
cin>>n;
memset(s, 0, sizeof s);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
s[i] = s[i-1] + a[i];
}

if (s[0] > s[n])    swap(s[0], s[n]);

LL s0 = s[0], sn = s[n];

sort(s, s + n + 1);

// 寻找 s0, sn 排序之后的位置
for (int i = 0; i <= n; i++)
{
if (s[i] == s0)
{
s0 = i;
break;
}
}
for (int i = n; i >= 0; i--)
{
if (s[i] == sn)
{
sn = i;
break;
}
}

// 装配方案
memset(st, false, sizeof st);   // 有了st数组，特别方便代码书写
int l = 0, r = n;
for (int i = s0; i >= 0; i -= 2)
{
a[l++] = s[i];
st[i] = true;
}
for (int i = sn; i <= n; i += 2)
{
a[r--] = s[i];
st[i] = true;
}

for (int i = 0; i <= n; i++)
{
if (!st[i])
{
a[l++] = s[i];
}
}

LL res = 0;
for (int i = 1; i <= n; i++)    res = max(res, abs(a[i] - a[i-1]));

cout<<res<<endl;
}
return 0;
}


/*

f[i][j]
1.0 a[i] == b[j]
f[i][j] = f[i+1][j-1]
2.0 a[i] != b[j]
f[i][j] = min(f[i+1][j] + 1, f[i][j-1] + 1);
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
char ch[N];
int f[N][N];
int n;

int main()
{
// input
scanf("%s", ch + 1);

// initial
n = strlen(ch + 1);
memset(f, 0, sizeof f);

// dp
for(int len = 2; len <= n; len++){
for(int i = 1; i + len - 1 <= n; i++){
static int j;
j = i + len - 1;
if(ch[i] == ch[j]){
f[i][j] = f[i+1][j-1];
}else{
f[i][j] = min(f[i+1][j] + 1, f[i][j-1] + 1);
}
}
}

// output
cout<<f[1][n]<<endl;

return 0;
}