Jackyc

9737

Jack_FuDan

hunzia
xiusike1
SUPERDOGE
crsecent
caoyiyang
Augety__

Peter_5

acWing_lbwnb
xiaohuahua
Randolph

Jackyc
14小时前

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 210, M = 30010;

bool g[N][N];
int match[N];
bool st[N];
int n, m;

bool dfs(int x) {
for(int i = 1; i <= n; i ++) {
if(!st[i] && g[x][i]) {
st[i] = true;
if(match[i] == -1 || dfs(match[i])) {
match[i] = x;
return true;
}
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
while(m --) {
int a, b;
scanf("%d%d", &a, &b);
g[a][b] = true;
}

for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
g[i][j] |= g[i][k] & g[k][j];
int ans = 0;
memset(match, -1, sizeof match);
for(int i = 1; i <= n; i ++) {
memset(st, false, sizeof st);
if(dfs(i)) ans ++;
}

printf("%d\n", n - ans);

return 0;
}


Jackyc
1天前
1024，工程课会打折吗请问

Jackyc
2天前
#include<iostream>
#include<cstring>
#include<algorithm>
#define sd(x) scanf("%d", &x)
#define rep(i, a, b) for(int i = a; i <= b; i ++)

using namespace std;

const int N = 50010;
int p[N];
int rela[N];
int n, k;
int x, y, r;
int ans;

void init() {
rep(i, 1, N - 1) {
p[i] = i;
rela[i] = 0;
}
}

int find(int x) {
if(x != p[x]) {
int root = find(p[x]);
rela[x] = (rela[x] + rela[p[x]]) % 3;
p[x] = root;
}
return p[x];
}

void merge(int r, int x, int y) {
int fx = find(x), fy = find(y);
if(fx != fy) {
p[fx] = fy;
rela[fx] = (rela[y] + r + 3 - rela[x]) % 3;
}
}

bool check(int r, int x, int y) {
if(x > n || y > n)
return false;
if(r == 1 && x == y)
return false;

if(find(x) == find(y)) {
int relation = (rela[x] + 3 - rela[y]) % 3;
return r == relation;
}
else
return true;
}
int main() {
init();
sd(n), sd(k);
while(k --) {
scanf("%d%d%d", &r, &x, &y);
r --;
if(check(r, x, y))
merge(r, x, y);
else ans ++;
}

printf("%d\n", ans);
return 0;
}



Jackyc
17天前

# I 三角尼姆

### 代码

#include<iostream>

using namespace std;

int main(){
int _;
cin >> _;
while(_ --){
int n;
cin >> n;
if(n * (n + 1) / 2 % 2 == 0) puts("Bob");
else puts("Alice");
}

return 0;
}


# G切圈圈

### 思路

#include<iostream>
#include<unordered_map>

using namespace std;

unordered_map<int, int> mp;

int main(){
ios::sync_with_stdio(false);
cin.tie(0);

int _;
cin >> _;
while(_ --){
int sum = 0, ans = 0;
mp.clear();
int n;
cin >> n;
while(n --){
int x;
cin >> x;
ans = max(ans, ++ mp[sum += x]);
}

cout << ans << endl;
}

return 0;
}


Jackyc
18天前

## C dd爱科学2.0

### 思路

sorry，简单DP, 为什么我只想到贪心, 赏自己两巴掌.

### 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define rep(a, b) for(int i = a; i <= b; i ++)
using namespace std;

const int N = 1000010;

int a[N];
char str[N];
int dp[N][26];

int main(){
int n;
cin >> n >> str + 1;

rep(1, n){
for(int j = 0; j < 26; j ++){
dp[i][j] = 1e9;
for(int k = 0; k <= j; k ++){
dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(str[i]-'A'-j));
}
}
}

int res = 1e9;
rep(0, 25){
res = min(res, dp[n][i]);
}

cout << res << endl;

return 0;
}


Jackyc
18天前

## DP适用

dp一般用于解决多阶段决策问题，即每个阶段都要做一个决策，全部的决策是一个决策序列，要你求一个

！！该问题具有最优子结构。

## DP硬核解释

DP的正规解释是：动态规划（英语：Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

## DP需要的三要素

• 状态表示
• 状态计算
• 边界

Jackyc
19天前
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define dbg(a)  cout<<#a<<" : "<<a<<endl;
#define IOS std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define PAUSE   system("pause")
#define sd(a)       scanf("%d",&a)
#define sll(a)      scanf("%intd",&a)
#define sdd(a,b)    scanf("%d%d",&a,&b)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sf(a)       scanf("%lf",&a)
#define sff(a,b)    scanf("%lf%lf",&a,&b)

{
int x = 0, fx = 1; char c = getchar();
while (c < '0' || c > '9') { fx ^= ((c == '-') ? 1 : 0); c = getchar(); }
while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
if (!fx) return -x;
return x;
}

#include <bits/stdc++.h>
#include <unordered_set>
//#include <unordered_map>
//#include <regex>
using namespace std;
#define ll long long
#define debug(x) cerr<<#x<<" : "<<x<<endl
//#define rep(i,_begin,_end) for (auto i=(_begin),_step=1-2*((_begin)>(_end));i!=_end;i+=_step)
#define MOD 1000000007
const double PI = acos(-1);
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> piii;
typedef unsigned long long ull;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
const int ddx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }, ddy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
// INPUT
template<typename T>
inline void in(T& x) {
T s = 0, w = 1; char ch = getchar();
while (ch < '0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
x = s * w;
}
// gcd
template<typename T>
T gcd(T a, T b) { return (!b) ? a : gcd(b, a % b); }
// min
template<class T>
T min(const vector<T>& v) { return *min_element(v.begin(), v.end()); }
// max
template<class T>
T max(const vector<T>& v) { return *max_element(v.begin(), v.end()); }
// lowbit
inline int lowbit(int x) { return x & (-x); }
inline int modadd(int x, int y) { return (x + y >= MOD ? x + y - MOD : x + y); }
// sgn
inline int sgn(int x) { return (x < 0 ? -1 : (x > 0 ? 1 : 0)); }
// ab
inline ll ab(ll x) { return x < 0 ? -x : x; }
#define modu MOD


Jackyc
21天前

## D 位运算之谜

### 输入

1
2 1


### 输出

0

#### 输入

1
2 2


### 输出

-1


### 思路

x ^ y = a - (b << 1)

### 代码

#include<iostream>

using namespace std;

typedef long long LL;

int main(){
int T;
scanf("%d", &T);
while(T --){
LL x, y;
scanf("%lld%lld", &x, &y);
LL ans = x - (y << 1);
if(ans < 0 || ans & y) cout << -1 << endl;
else cout << ans << endl;
}

return 0;
}


### 思路

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

char p[N], s[N];
int ne[N];
int main(){
scanf("%s", p + 1);
int n = strlen(p + 1);
for(int i = 2, j = 0; i <= n; i ++){
while(j && p[j + 1] != p[i]) j = ne[j];
if(p[i] == p[j + 1]) j ++;
ne[i] = j;
}

int T;
int ans = 0;
scanf("%d", &T);
while(T --){
scanf("%s", s + 1);
int m = strlen(s + 1);
int res = 0;
for(int i = 1, j = 0; i <= m; i ++){
while(j && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j ++;
res = max(res, j);
}
ans += res;
}

printf("%d\n", ans);

return 0;
}


### 思路

#include<iostream>
#include<cstring>
#include<algorithm>
#define rep(a, b) for(int i = a; i <= b; i ++)
using namespace std;

const int N = 200100;

int p[N];
int w[N];
int Size[N];
int n;
int ans[N];

int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}

int main(){
scanf("%d", &n);
rep(1, n){
int x;
scanf("%d", &x);
w[i] = x;
p[i] = i;
Size[i] = 1;
}

rep(1, n - 1){
int a, b;
scanf("%d%d", &a, &b);
if(w[a] == w[b]) {
int pa = find(a), pb = find(b);
if(pa == pb) continue;
Size[pb] += Size[pa];
p[pa] = pb;
}
}
int maxv = 0;
rep(1, n){
maxv = max(maxv, Size[find(p[i])]);
}

int cnt = 0;
rep(1, n){
if(Size[find(p[i])] == maxv) ans[cnt ++] = i;
}

sort(ans, ans + cnt);
printf("%d\n", cnt);
rep(0, cnt - 1){
printf("%d ", ans[i]);
}
cout << endl;
}


Jackyc
23天前

## C 杨辉三角

### 输入样例

3


### 输出样例

6


### 代码

#include<iostream>

using namespace std;

typedef long long LL;

const int mod = 99824353;

LL qmi(LL a, LL b){
if(b < 0) return 1;
LL res = 1;
while(b){
if(b & 1) res = (LL)res * a % mod;
a = (LL)a * a % mod;
b >>= 1;
}

return res % mod;
}
int main(){
LL n;
cin >> n;
if(n == 2) {
cout << 1 << endl;
return 0;
}
n --;
cout << n % mod * (n + 1) % mod * qmi(2, n - 2) % mod << endl;
}


## B最短串

abc
?de

5

### 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 5010;
string a, b;

bool check(int i, int j){
if(a[i] == '?' || b[j] == '?' || a[i] == b[j]) return true;
return false;
}

int main(){
cin >> a >> b;

int j = 0;
for(int i = 0; i < a.size(); i ++){
if(j == (int)b.size()) break;
if(check(i, j)) j ++;
else {
j = 0;
if(check(i, j)) j ++;
}
}

int ans1 = a.size() + (b.size() - j);

j = 0;
for(int i = 0; i < b.size(); i ++){
if(j == (int)a.size()) break;
if(check(j, i)) j ++;
else {
j = 0;
if(check(j, i)) j ++;
}
}

int ans2 = b.size() + (a.size() - j);

int ans = min(ans1, ans2);

cout << ans << endl;

return 0;
}


## H卷王之王

### 输入

5 2
1 2 3 4 5
2
3


### 输出

6 4 6 4 5


### 思路

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define pre(i, a, b) for(int i = a; i >= b; i --)
#define N 100005
using namespace std;
struct Node{
int l, r;
int val;
}tr[N << 2];
int n, m, a[N];
#define L tr[u].l
#define R tr[u].r
#define ls (u << 1)
#define rs (ls | 1)
#define S tr[u].val

void build(int u, int l, int r){
L = l, R = r;
if(l == r) S = a[l];
else {
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
//pushup
S = min(tr[ls].val, tr[rs].val);
}
}

void modify(int u, int val){
if(S > val) return;
if(L == R) S += val;
else {
if(tr[ls].val <= val) modify(ls, val);
if(tr[rs].val <= val) modify(rs, val);
S = min(tr[ls].val, tr[rs].val);
}
}

void query(int u){
if(L == R) printf("%d ", S);
else query(ls), query(rs);
}

int main(){
scanf("%d%d", &n, &m);
rep(i, 1, n) scanf("%d", &a[i]);
build(1, 1, n);
while(m --){
int x;
scanf("%d", &x);
if(x == 0) continue;
modify(1, x);
}

query(1);

return 0;
}


## 哥三好

### 解法：

6种情况, a人 花 2, 3, 5 b人 花 2, 3, 5, c人花2， 3，5

#include<iostream>

using namespace std;

const int N = 110, mod = 1000000007;
int f[N][N][N];
int main(){
int a, b, c;
cin >> a >> b >> c;
a /= 150;
b /= 150;
c /= 150;

for(int i = 0; i <= 1; i ++)
for(int j = 0; j <= 1; j ++)
for(int k = 0; k <= 1; k ++)
f[i][j][k] = 1;

for(int i = 0; i <= a; i ++)
for(int j = 0; j <= b; j ++)
for(int k = 0; k <= c; k ++){
if(i >= 2) f[i][j][k] = (f[i][j][k] + f[i - 2][j][k]) % mod;
if(i >= 3) f[i][j][k] = (f[i][j][k] + f[i - 3][j][k]) % mod;
if(i >= 5) f[i][j][k] = (f[i][j][k] + f[i - 5][j][k]) % mod;

if(j >= 2) f[i][j][k] = (f[i][j][k] + f[i][j - 2][k]) % mod;
if(j >= 3) f[i][j][k] = (f[i][j][k] + f[i][j - 3][k]) % mod;
if(j >= 5) f[i][j][k] = (f[i][j][k] + f[i][j - 5][k]) % mod;

if(k >= 2) f[i][j][k] = (f[i][j][k] + f[i][j][k - 2]) % mod;
if(k >= 3) f[i][j][k] = (f[i][j][k] + f[i][j][k - 3]) % mod;
if(k >= 5) f[i][j][k] = (f[i][j][k] + f[i][j][k - 5]) % mod;
}

cout << f[a][b][c] % mod<< endl;

return 0;
}


Jackyc
23天前

## B擅长解密的小红同学

### 多重排列数

$$\frac{(\sum_{i=1}^{k}n_i)!}{\prod_{i=0}^{k}n_i!}$$

### 代码

#include<iostream>

using namespace std;

const int mod = 1e9 + 7;
const int N = 1e7 + 10;
typedef long long LL;

int a[10];
LL fact[N], infact[N];

LL qmi(LL a, LL b){
LL res = 1;
while(b){
if(b & 1) res = (LL)res * a % mod;
a = (LL) a * a % mod;
b >>= 1;
}
return res;
}

void init(){
fact[0] = infact[0] = 1;
for(int i = 1; i < N; i ++){
fact[i] = (LL)fact[i - 1] * i % mod;
}

}
int main(){
for(int i = 0; i < 10; i ++)
cin >> a[i];

init();

LL fz = 0;
LL ans = 1;
for(int i = 0; i < 10; i ++){
fz = (LL)(fz + a[i]) % mod;
ans = (LL)ans * fact[a[i]] % mod;
}
ans = (LL)fact[fz] * qmi(ans, mod - 2) % mod;

cout << ans << endl;

return 0;
}


## H 漂亮数

### 代码

#include<iostream>
#include<cstring>

using namespace std;

const int N = 50000010;

typedef long long LL;
LL primes[N];
int cnt;
LL st[N];
int s[N * 2];

void init(){
for(int i = 2; i < N; i ++){
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; (LL)primes[j] * i < N; j ++){
st[(LL)primes[j] * i] = 1;
if(i % primes[j] == 0) break;
}
}
for(int i = 0; i < cnt; i ++)
for(int j = 0; j < cnt; j ++){
if((LL)primes[i] * primes[j] >= N * 2) break;
s[(LL)primes[i] * primes[j]] = 1;
}

for(int i = 1; i <= N * 2; i ++)
s[i] += s[i - 1];
}

int main(){
init();
int T;
cin >> T;
while(T --){
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
}
return 0;
}


## I 加减

### 输入描述

$1≤n≤10^5$
$1≤k≤10^{12}$
$1≤ai≤10^9$

### 输出描述:

不超过  次操作之后，数组中可能出现最多次数元素的次数。


### 输入

5 3
6 3 20 8 1


### 输出

2


### 说明

共 3 次操作如下：



### 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;

LL a[N];
LL s[N];
LL n, k;

bool check(int l, int r){
int mid = l + r >> 1;
LL left_op = a[mid] * (mid - l + 1) - (s[mid] - s[l - 1]);
LL right_op = (s[r] - s[mid]) - a[mid] * (r - mid);
return (left_op + right_op) <= k;
}

int main(){
scanf("%lld%lld", &n, &k);

for(int i = 1; i <= n; i ++){
scanf("%lld", &a[i]);
}

sort(a + 1, a + n + 1);

for(int i = 1; i <= n; i ++)
s[i] = s[i - 1] + a[i];
int res = 1;
for(int i = 1; i <= n; i ++){
//枚举左端点
int l = i, r = n;
//二分右端点
while(l < r){
int mid = l + r + 1>> 1;
if(check(i, mid)){
l = mid;
}
else r = mid - 1;
}

res = max(res, r - i + 1);
}

cout << res << endl;
}