__yxc_

345

Chanson4
itdef
acwing_1048
uaN_1

virapaksa

Q_1.Forver

__yxc_
6天前
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcount __builtin_popcount

int cnt;
map<int, int> mapp;
const int N = 2e5 + 10;
int discrete(int x){
if (!mapp.count(x)) mapp[x] = cnt++;
return mapp[x];
}

//int a[200341] = {0};
int main(){
//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n;
vi a(N, 0);
mapp.clear();
cnt = 0;
for (int i = 0, t; i < n; ++i){
cin >> t;t = discrete(t);
a[t] += 1;
}
cin >> m;
int happy = 0, ok = 0, ans = 1;
set<int> sett;
vvi b(N, vi(2, 0));
for (int i = 0; i < m; ++i) cin >> b[i][0];
for (int i = 0; i < m; ++i) cin >> b[i][1];
for (int i = 0; i < m; ++i){
int t = discrete(b[i][0]);
if (a[t] > happy){
happy = a[t];
ans = i + 1;
ok = a[discrete(b[i][1])];
}
else if (happy == a[t] && ok < a[discrete(b[i][1])]){
ok = a[discrete(b[i][1])];
ans = i + 1;
}
}

cout << ans << endl;
return 0;
}



__yxc_
6天前
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcount __builtin_popcount

int cnt;
map<int, int> mapp;
const int N = 2e5 + 10;
int discrete(int x){
if (!mapp.count(x)) mapp[x] = cnt++;
return mapp[x];
}

//int a[200341] = {0};
int main(){
//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n;
vi a(N, 0);
mapp.clear();
cnt = 0;
for (int i = 0, t; i < n; ++i){
cin >> t;t = discrete(t);
a[t] += 1;
}
cin >> m;
int happy = 0, ok = 0, ans = -1;
set<int> sett;
vvi b(N, vi(2, 0));
for (int i = 0; i < m; ++i) cin >> b[i][0];
for (int i = 0; i < m; ++i) cin >> b[i][1];
for (int i = 0; i < m; ++i){
//if (i > 1000) cout << b[i][0] << " \n"; 重点是这一句，数据有2000个，但是读到省略号以后的数据全是0
int t = discrete(b[i][0]);
if (a[t] > happy){
happy = a[t];
ans = i + 1;
ok = a[discrete(b[i][1])];
}
else if (happy == a[t] && ok < a[discrete(b[i][1])]){
ok = a[discrete(b[i][1])];
ans = i + 1;
}
}

cout << ans << endl;
return 0;
}

//下面这种写法是第2000个数据第一千多就读到了，根本没法跑代码

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcount __builtin_popcount

int cnt;
map<int, int> mapp;
int discrete(int x){
if (!mapp.count(x)) mapp[x] = cnt++;
return mapp[x];
}

//int a[200341] = {0};
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n;
vi a(2e5, 0);
mapp.clear();
cnt = 0;
for (int i = 0, t; i < n; ++i){
cin >> t;t = discrete(t);
a[t] += 1;
}
cin >> m;
int happy = 0, ok = 0, ans = -1;
set<int> sett;
for (int i = 1; i <= m; ++i){
int t;  cin >> t; t = discrete(t);
if (a[t] > happy){
happy = a[t];
sett.clear();
sett.insert(i);
ans = i;
}
else if (a[t] == happy){
sett.insert(i);
}
}
for (int i = 1; i <= m; ++i) {
int t; cin >> t; t = discrete(t);
if (sett.count(i) && ok < a[t]){
ok = a[t];
ans = i;
}
}
cout << ans << endl;
return 0;
}


__yxc_
6天前

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcount __builtin_popcount

int cnt;
map<int, int> mapp;
const int N = 2e5 + 10;
int discrete(int x){
if (!mapp.count(x)) mapp[x] = cnt++;
return mapp[x];
}

//int a[200341] = {0};
int main(){
//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n;
vi a(N, 0);
mapp.clear();
cnt = 0;
for (int i = 0, t; i < n; ++i){
cin >> t;t = discrete(t);
a[t] += 1;
}
cin >> m;
int happy = 0, ok = 0, ans = 1;
set<int> sett;
vvi b(N, vi(2, 0));
for (int i = 0; i < m; ++i) cin >> b[i][0];
for (int i = 0; i < m; ++i) cin >> b[i][1];
for (int i = 0; i < m; ++i){
//if (i > 1000) cout << b[i][0] << " \n"; 重点是这一句，数据有2000个，但是读到省略号以后的数据全是0
int t = discrete(b[i][0]);
if (a[t] > happy){
happy = a[t];
ans = i + 1;
ok = a[discrete(b[i][1])];
}
else if (happy == a[t] && ok < a[discrete(b[i][1])]){
ok = a[discrete(b[i][1])];
ans = i + 1;
}
}

cout << ans << endl;
return 0;
}

//下面这种写法是第2000个数据第一千多就读到了，根本没法跑代码

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcount __builtin_popcount

int cnt;
map<int, int> mapp;
int discrete(int x){
if (!mapp.count(x)) mapp[x] = cnt++;
return mapp[x];
}

//int a[200341] = {0};
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n;
vi a(2e5, 0);
mapp.clear();
cnt = 0;
for (int i = 0, t; i < n; ++i){
cin >> t;t = discrete(t);
a[t] += 1;
}
cin >> m;
int happy = 0, ok = 0, ans = 1;
set<int> sett;
for (int i = 1; i <= m; ++i){
int t;  cin >> t; t = discrete(t);
if (a[t] > happy){
happy = a[t];
sett.clear();
sett.insert(i);
ans = i;
}
else if (a[t] == happy){
sett.insert(i);
}
}
for (int i = 1; i <= m; ++i) {
int t; cin >> t; t = discrete(t);
if (sett.count(i) && ok < a[t]){
ok = a[t];
ans = i;
}
}
cout << ans << endl;
return 0;
}



CF已AC，我是真服了..debug两个小时原来是网站有问题，以后再也不相信网站了

__yxc_
8天前
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcount __builtin_popcount

class FenwickTree{
private:
vll ft;
void build(const vll& f){
int m = sz(f) - 1;
ft.assign(m + 1, 0);
for (int i = 1; i <= m; ++i){
ft[i] += f[i];
if (i + lowbit(i) <= m) ft[i + lowbit(i)] += f[i];
}
}
public:
FenwickTree(int m){ft.assign(m + 1, 0);}
FenwickTree(const vll& f){
int m = sz(f) - 1;
ft.assign(m + 1, 0);
build(f);
}
void update(int i, ll val){
while (i < sz(ft)){
ft[i] += val;
i += lowbit(i);
}
}
ll rsq(int i){
ll sum = 0;
while (i){sum += ft[i]; i -= lowbit(i);}
}
ll rsq(int i, int j){return rsq(j) - rsq(i - 1);}

};
int numFactors(int x){
int result = 2;
for (int i = 2; i <= x / i; ++i){
if (x % i == 0){
if (x / i != i) result += 1;
result += 1;
}
}
return result;
}

vi sieveFactors(int x){
vi result(x + 1, 0);
for (int i = 1; i <= x; ++i){
for (int j = i; j <= x / i; ++j){
result[j * i] += 1;
}
}
return result;
}

int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
/*
int n = 2e9;
vi a= sieveFactors(n);
vi result;
cout << sz(a) << endl;
int maxx = 1;
for (int i = 1; i <= n; ++i){
if (maxx < a[i]){
result.pb(i);
maxx = a[i];
}
}
cout << sz(result) << endl;
for (auto x : result) cout << x << ",";*/
set<int> sett{1, 2, 4, 6, 12,24,36,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,
498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,
61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360};
int n;
cin >> n;
auto t = sett.lower_bound(n);
if (t == sett.end() || *t > n) --t;
cout << *t << endl;
return 0;
}



__yxc_
8天前
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcount __builtin_popcount

void dfs(const int& n, bitset<10>& bs, vi& b, int k){
if (k == n + 1){
for (int i = 1; i <= n; ++i) cout << b[i] << " \n"[i == n];
return;
}
for (int i = 1; i <= n; ++i){
if (bs[i]) continue;
bs[i] = 1;
b[k] = i;
dfs(n, bs, b, k + 1);
bs[i] = 0;
}
}

int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vi b(n + 1);
bitset<10> bs;
dfs(n, bs, b, 1);
return 0;
}



__yxc_
8天前
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcount __builtin_popcount

//小失误，在编程的时候忘记把计数放到循环里面，而是放到了外面，重复计数了。
//先枚举第一行的所有按法，然后从第二行开始根据上面的灯的情况向下传递
//最后判断最后一行即可

void change(vvi& a, int i, int j){
a[i][j] ^= 1;
if (i) a[i - 1][j] ^= 1;
if (i < 4) a[i + 1][j] ^= 1;
if (j) a[i][j - 1] ^= 1;
if (j < 4) a[i][j + 1] ^= 1;
}

int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int TC;
cin >> TC;
while (TC--){
vvi a(5, vi(5));
int result = 1e7;
for (int i = 0; i < 5; ++i) {
string s;
cin >> s;
for (int j = 0; j < 5; ++j) {a[i][j] = s[j] - '0';}
}
auto b = a;
for (int i = 0; i < (1 << 5); ++i){
int j = i, k = 0;
a = b;
int cnt = 0;
while (k < 5){
if (j & (1 << k)) {change(a, 0, k);cnt += 1;}
k += 1;
}
for (int j = 1; j < 5; ++j){
for (int k = 0; k < 5; ++k) if (a[j - 1][k] == 0){
change(a, j, k);
cnt += 1;
}
}
bool ok = true;
for (int j = 0; j < 5; ++j) {
if (a[4][j] == 0) {ok = false; break;}
}
if (ok) result = min(result, cnt);
}
cout << (result <= 6 ? result : -1) << endl;
}
return 0;
}



__yxc_
8天前
//关键在于如何保证序列递增且不重复，那么考虑接下来的位置时，就必须从当前位置的下一个数字开始搜索（这个序列必须有序）
//这样可以保证递增，但是一定保证不重复吗？答案是正确的，因为重复的原因都是因为大数在前面，小数在后面，排序后重复
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcnt __builtin_popcount

void dfs(const int& n, const int& m, vi& b, bitset<100>& bs, int k, int start){
if (k == m){
for (int i = 0; i < m; ++i) cout << b[i] << " \n"[i + 1 == m];
}
for (int i = start; i <= n; ++i){
if (bs[i]) continue;
bs[i] = 1;
b[k] = i;
dfs(n, m, b, bs, k + 1, i + 1);
bs[i] = 0;
}
}

int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
if(!m) return 0;
vi b(m + 10);
bitset<100> bs;
dfs(n, m, b, bs, 0, 1);
return 0;
}



__yxc_
8天前

//第一思路居然是写两个并查集，一个维护都相等的集合，一个维护不相等的集合，但是有一些测试数据跑不过去
//比如 1 7 1， 7 9 0， 13 9 1， 1 13 1，然后用了al维护，结果还是不行
//思路应该是：用一个uf维护相等的集合，在保存所有的不相等的点，在结束后判断一下不相等的点有没有在一个set中的即可
//或者维护所有不相等的点，然后存储相等的点对，最后看相等的点对有没有在一个集合中的即可  //不行的，只能维护相等的点
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef vector<vi> vvi;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcnt __builtin_popcount

class UnionFind{
private:
vi fa;
public:
UnionFind(int m){
fa.assign(m, 0); for (int i = 0 ; i < m; ++i) fa[i] = i;
}
int findSet(int x){return fa[x] == x ? x : fa[x] = findSet(fa[x]);}
bool isSameset(int x, int y){return findSet(x) == findSet(y);}
void unionSet(int x, int y){
x = findSet(x), y = findSet(y);
if (x == y) return;
fa[x] = y;
}
};

map<int, int> mapp;
int cnt;
int discrete(int x){
if (mapp.count(x) == 0) mapp[x] = cnt++;
return mapp[x];
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int tc;
cin >> tc;
while (tc--){
int n;
cin >> n;
UnionFind uf(2 * n + 10);
mapp.clear();
cnt = 0;
bool ok = true;
vii a;
for (int i = 0; i < n; ++i){
int u, v, p;
cin >> u >> v >> p;
u = discrete(u);
v = discrete(v);
if (ok == false) continue;
if (u == v) {ok = p == 1; continue;}
if (p == 1){
uf.unionSet(u, v);
}
else{
a.pb({u, v});
}
}
for (auto& x : a) if (uf.isSameset(x.first, x.second)){
ok = false;
break;
}
cout << (ok ? "YES" : "NO") << endl;
}
return 0;
}



__yxc_
9天前
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcnt __builtin_popcount

//题目大意：想办法排列，满足行和列的单调性。
//已知的信息：行数和每行的人数，且行数范围最大是5，总人数不会超过30个

//爆搜：感觉有点像背包问题，这个状态可以由5个子状态推过来，但是只有满足条件的子状态才能往这个状态推
//对于子状态的判断，只有行人数的判断和跟相邻行关系的判断，有个疑问就是为什么没有当前放置同学的编号的判断呢？
//初始条件，1只能放在1号位

//总的疑问：为什么可以直接按人数进行转移呢 不需要对状态的最后一个同学的编号进行判定吗

ll f[31][31][31][31][31] = {0};//vector写不出五维的东西..

ll dfs(int a, int b, int c, int d, int e){
ll& ans = f[a][b][c][d][e];cout << a << b << c << d << e << endl;
if (ans) return ans;

if (a - 1 >= b && a >= 1)ans += dfs(a - 1, b, c, d, e);
if (b - 1 >= c && b >= 1)ans += dfs(a, b - 1, c, d, e);
if (c - 1 >= d && c >= 1)ans += dfs(a, b, c - 1, d, e);
if (d - 1 >= e && d >= 1)ans += dfs(a, b, c, d - 1, e);
if (e >= 1)ans += dfs(a, b, c, d, e - 1);
return ans;
}

int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int k;
f[1][0][0][0][0] = 1;       //边界条件
while (cin >> k && k){
vi A(5, 0);
for (int i = 0; i < k; ++i) cin >> A[i];
cout << dfs(A[0], A[1], A[2], A[3], A[4]) << endl;
}
return 0;
}



__yxc_
9天前
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef unsigned long long ull;

#define lowbit(S) ((S)& -(S))
#define pb push_back
#define sz(x) ((int)(x.size()))
#define bg begin()
#define ed end()
#define rbg rbegin()
#define red rend()
#define bitcnt __builtin_popcount

//求限定了最小长度连续区间的最大平均值，第一想法是枚举所有区间， tle
//平均值没有递增效应， 可以知道平均值的范围，对范围内的平均值进行判定，看看是否符合
//对平均值进行判定，可以将每个数都减去平均值，如果存在长度大于f的连续区间和>=0,满足条件
bool check(const vi& a, int f, double ave){
int n = sz(a) - 1;
double minn = 1e3, maxx = -1e3;
vector<double> s(n + 1, 0);
for (int i = 1; i <= n; ++i){
s[i] = s[i - 1] + (double)a[i] - ave;
}
for (int r = f; r <= n; ++r){
minn = min(minn, s[r - f]);
maxx = max(maxx, s[r] - minn);
}
return maxx >= 0;
}

int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, f, result = 0;
double l = 0, rr = 0;
cin >> n >> f;
vi a (n + 1);
for (int i = 1; i <= n; ++i) {cin >> a[i];rr = max(rr, double(a[i]));}
while (rr - l > 1e-4){
double mid = (l + rr) / 2;
if (check(a, f, mid)) {l = mid;}
else rr = mid;
}
cout << int(rr * 1000) << endl;
return 0;
}