2018-07-25
很神奇的一道题,要求用尽量少的笔数,把整个图画完,每笔不重合. 类似于一笔画问题. 题目保证的可行,所以只要将每个联通块里度数为奇数的点连起来,dfs一笔画,然后再把自己连的边删掉就行了
/* ***********************************************
Author :JiangYu
Created Time :2018年07月27日 星期五 13时57分29秒
File Name :3.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1024;
int n, m;
vector<int> g[N], ans[N];
int fa[N];
int getfa(int k) {
if(k != fa[k]) fa[k] = getfa(fa[k]);
return fa[k];
}
int deg[N];
bool vis[N << 2];
void unio(int x, int y) {
int fax = getfa(x);
int fay = getfa(y);
fa[fax] = fay;
}
struct edge{
int to, nex;
}ed[N << 3];
int head[N], cnt;
int stk[N<<2];
void add(int u, int v) {
cnt++;
ed[cnt].to = v;
ed[cnt].nex = head[u];
head[u] = cnt;
}
int top;
void dfs(int u) {
for(int &v = head[u]; v; v = ed[v].nex) {
//cout << v << endl;
if(vis[v>>1]) continue;
int t = v;
vis[v>>1] = 1;
dfs(ed[v].to);
stk[++top] = (t&1? -(t>>1) : t>>1);
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d", &n, &m) != EOF){
memset(head, 0, sizeof head);
memset(deg, 0, sizeof deg);
memset(vis, 0, sizeof vis);
cnt = 1;
for(int i = 1; i <= n; ++i)
g[i].clear(), ans[i].clear(), fa[i] = i;
for(int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
deg[u]++;
deg[v]++;
unio(u, v);
}
for(int i = 1; i <= n; ++i) {
if(deg[i]&1) g[getfa(i)].push_back(i);
}
int w = 0;
for(int i = 1; i <= n; ++i)
if(getfa(i) == i) {
if(!g[i].size()) {
top = 0;
dfs(i);
++w;
while(top)
ans[w].push_back(stk[top--]);
}
else {
for(int j = 0; j < g[i].size(); j += 2) {
add(g[i][j], g[i][j+1]),
add(g[i][j+1], g[i][j]);
}
top = 0;
dfs(i);
vector<int> pos;
for(int i = top; i; --i)
if(stk[i] > m || stk[i] < -m)
pos.push_back(i);
for(int i = 0; i < pos.size()-1; ++i) {
w++;
for(int j = pos[i]-1; j > pos[i+1]; j--)
ans[w].push_back(stk[j]);
}
w++;
for(int j = pos[pos.size()-1] - 1; j; --j) {
ans[w].push_back(stk[j]);
}
for(int j = top; j > pos[0]; --j)
ans[w].push_back(stk[j]);
}
}
int t = w;
for(int i = 1; i <= w; ++i)
if(ans[i].size() == 0) t--;
cout << t<< endl;
for(int i = 1; i <= w; ++i) {
if(ans[i].size() != 0) {
printf("%d", ans[i].size());
for(int j = 0; j < ans[i].size(); ++j) {
printf(" %d", ans[i][j]);
}
puts("");
}
}
}
return 0;
}
1是所有数字的因数, 那么在2~n中. 假设存在k为必胜态.Alice拿K 以及1.获胜 假设不存在,Alice拿走1,将必败态转移给Bob 所以先手必胜
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int a;
while(cin>>a) puts("Yes");
return 0;
}
构造题要命啊~~~
/* ***********************************************
Author :JiangYu
Created Time :2018年07月27日 星期五 15时59分02秒
File Name :5.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
int p;
bool grid[3010][3010];
int main() {
p=47;
rep(i,0,p) rep(j,0,p) {
rep(k,0,p) grid[i*p+j][k*p+(j*k+i)%p]=1;
}
puts("2000");
rep(i,0,2000) {
rep(j,0,2000) printf("%d",grid[i][j]);
puts("");
}
}
所谓的容斥基础练习??
/* ***********************************************
Author :JiangYu
Created Time :2018年07月26日 星期四 10时46分55秒
File Name :6.cpp
************************************************ */
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e3 + 256;
ll fac[N], fnv[N];
int pw[N*N];
int gg[N][N];
ll f[N][N];
ll mod = 998244353;
ll quick(ll x, int y) {
ll ans = 1;
while(y) {
if(y&1) ans = x * ans % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
fac[0] = fnv[0] = 1;
for(int i = 1; i < N ; ++i) fac[i] = fac[i-1] * i % mod, fnv[i] = quick(fac[i], mod-2);
pw[0] = 1;
for(int i = 1; i <= 9000000; ++i) pw[i] = pw[i - 1] * 2 % mod;
for(int w = 0; w <= 3000; ++w) for(int z = 0; z <= 3000; ++z)
gg[w][z] = pw[w*z] * fnv[w] % mod * fnv[z] % mod;
for(int s = 0; s <= 3001; ++s) {
for(int u = s; u >= 0; u--) {
int val = fnv[u] * fnv[s-u] % mod;
if((s-u) % 2 ) val = mod - val;
f[s][u] = (f[s][u+1] + val) % mod;
}
}
return 0;
}
线段树维护区间距离下一次变动的最小值,到了才往下更新. 队友就是强啊
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 1e5 + 5;
int a[N];
struct Segtree{
#define ls o << 1
#define rs o << 1 | 1
#define MID int mid = e[o].l + e[o].r >> 1
struct Node{
int l, r, t, ans, lazy;
}e[N << 2];
void build(int o, int l, int r)
{
e[o].l = l, e[o].r = r;
e[o].lazy = 0;
if (l == r)
{
e[o].ans = 0;
e[o].t = a[l];
return;
}
MID;
build(ls, l, mid);
build(rs, mid + 1, r);
up(o);
}
void up(int o)
{
e[o].ans = e[ls].ans + e[rs].ans;
e[o].t = min(e[ls].t - e[ls].lazy, e[rs].t - e[rs].lazy);
}
void down(int o)
{
// cout << "down: " << o << " " << e[o].lazy << " " << e[o].t << endl;
if (e[o].lazy)
{
add(ls, e[ls].l, e[ls].r, e[o].lazy);
add(rs, e[rs].l, e[rs].r, e[o].lazy);
e[o].lazy = 0;
}
}
void add(int o, int l, int r, int val)
{
// cout << "add:" << e[o].t << " " << e[o].l << " " << e[o].r << " " << val << endl;
if (e[o].l == e[o].r)
{
// e[o].ans += (val - e[o].t) / a[l];
// e[o].ans += (val >= e[o].t);
// e[o].t = (val - e[o].t) % a[l] + a[l];
if (val >= e[o].t)
{
e[o].ans += (val - e[o].t) / a[l] + 1;
e[o].t = a[l] - (val - e[o].t) % a[l];
}
else e[o].t -= val;
return;
}
if (e[o].l == l && e[o].r == r)
{
e[o].lazy += val;
if (e[o].lazy >= e[o].t) down(o), up(o);
return;
}
// cout << "___" << endl;
MID;
down(o);
if (r <= mid) add(ls, l, r, val);
else if (l > mid) add(rs, l, r, val);
else add(ls, l, mid, val), add(rs, mid + 1, r, val);
up(o);
// cout << "add:" << e[o].t << " " << e[o].l << " " << e[o].r << " " << val << endl;
}
int query(int o, int l, int r)
{
if (e[o].l == l && e[o].r == r)
{
// cout << "__:" << o << " " << e[o].ans << endl;
return e[o].ans;
}
down(o);
up(o);
MID;
if (r <= mid) return query(ls, l, r);
else if (l > mid) return query(rs, l, r);
else return query(ls, l, mid) + query(rs, mid + 1, r);
}
}tree;
int main()
{
int n, q;
while (scanf("%d%d", &n, &q) == 2)
{
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
tree.build(1, 1, n);
char op[10];
while (q--)
{
int l, r; scanf("%s%d%d", op, &l, &r);
if (op[0] == 'a') tree.add(1, l, r, 1);
else printf("%d\n", tree.query(1, l, r));
// cout << "___" << tree.e[8].ans << endl;
// for (int i = 1; i <= 10; i++) cout << tree.e[i].ans << " ";
// cout << endl;
}
}
return 0;
}
在只能交换相邻项的条件下,交换数就是逆序对数. ans = 逆序对数 * min(x, y)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 1e5 + 5;
struct Node{
int a[N], n;
void init(int _n)
{
n = _n;
memset(a, 0, sizeof a);
}
void add(int i)
{
for (; i <= n; i += i & -i) a[i]++;
}
int sum(int i)
{
int ret = 0;
for (; i; i -= i & -i) ret += a[i];
return ret;
}
}bit;
int a[N], b[N];
int main()
{
int n, x, y;
while (scanf("%d%d%d", &n, &x, &y) == 3)
{
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b, b + n);
bit.init(n);
ll ans = 0;
for (int i = 0; i < n; i++)
{
int k = lower_bound(b, b + n, a[i]) - b + 1;
ans += i - bit.sum(k);
bit.add(k);
}
printf("%lld\n", ans * min(x, y));
}
return 0;
}