10.11 Updata : 烦死了。。。麻烦死了。。。不补了。。就这些吧
20171001
上：
100 + 90 + 90 = 280 = rank 8
T1
/*
T1
从最大的数开始倒着枚举
暴力分解每位判断是否可行
*/
#include <cstdio>
#define rg register
int main (int argc, char *argv[])
{
freopen ("bit.in", "r", stdin); freopen ("bit.out", "w", stdout);
int N, c = , K = ; scanf ("%d", &N); rg int i, j, r;
r = N; for (; r; r /= ) K += r % ; -- K;
for (i = N - ; i >= ; -- i)
{
for (r = i, c = ; r; r /= ) c += r % ;
if (c == K) return printf ("%d", i), ;
}
return ;
}
T2
/*
T2
做一个类似于背包一样的dp预处理出所有可能的n的答案就好了
可以预先打个表，方便计算
*/
#include <cstdio>
#include <iostream>
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
std :: string Name = "stick", _I = ".in", _O = ".out";
#define Max 200
int a[] = { , , , , , , , , , };
typedef long long LL; LL f[Max];
#ifdef WIN32
#define PLL "%I64d"
#else
#define PLL "%lld"
#endif
inline void cmin (LL &a, LL b) { if (b < a) a = b; }
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N; read (N); rg int i, j;
f[] = , f[] = , f[] = , f[] = , f[] = , f[] = ;
for (i = ; i <= ; ++ i)
{
f[i] = f[i - a[]] * ;
for (j = ; j <= ; ++ j)
if (f[i - a[j]] != ) cmin (f[i], f[i - a[j]] * + j);
}
printf (PLL" ", f[N]);
if (N % == ) printf (""), N -= ;
for (; N; printf (""), N -= ); return ;
}
T3
/*
T3
滑动窗口的思想
每滑动一下，区间就会加一个元素，少一个元素
对应计算即可
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
#define Max 100009
int v[Max], s[], c[Max]; bool is[Max];
inline void Modi (int p, int t)
{
int r = v[p];
if (!c[r]) -- s[]; if (c[r] == ) -- s[]; if (c[r] > ) -- s[];
c[r] += t;
if (!c[r]) ++ s[]; if (c[r] == ) ++ s[]; if (c[r] > ) ++ s[];
}
inline int min (int a, int b) { return a < b ? a : b; }
int main (int argc, char *argv[])
{
freopen ("music.in", "r", stdin); freopen ("music.out", "w", stdout);
int N, M, Answer = , L; read (N), read (M); rg int i, j;
for (i = ; i <= M; ++ i) read (v[i]);
for (i = M, s[] = N; i >= ; -- i)
{
Modi (i, ); if (i + N <= M) Modi (i + N, -);
if (!s[] && (i + N > M || is[i + N])) is[i] = true;
}
memset (c, , sizeof c); s[] = N, s[] = , s[] = ;
for (i = , L = min (N - , M); i <= L; ++ i)
{
if (i) Modi (i, );
if (!s[] && s[] == N - i && (i + > M || is[i + ])) ++ Answer;
if (i == M && !s[] && s[] == N - i && (i + > M || is[i + ])) Answer += N - M - ;
}
printf ("%d", Answer); return ;
}
下
40 + 40 + 100 = 180 = rank 17
T1
/*
T1
结论题
容易发现是每条边两点点权和与边权之比取大
*/
#include <cstdio>
#include <iostream>
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
#define Max 1000004
typedef double flo; int c[Max];
inline void cmax (flo &a, flo b) { if (b > a) a = b; }
std :: string Name = "graph", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, M, x, y, z; flo s = ; read (N), read (M); rg int i;
for (i = ; i <= N; ++ i) read (c[i]);
for (i = ; i <= M; ++ i)
read (x), read (y), read (z), cmax (s, (c[x] + c[y]) / (z + 0.0));
printf ("%.2lf", s); return ;
}
T2
/*
T2
枚举可能的高度
贪心验证是否可行
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#define Max 2009
#define INF (1e9)
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
std :: string Name = "photo", _I = ".in", _O = ".out";
bool Comp (int a, int b) { return a > b; } int a[Max], b[Max];
inline void cmin (int &a, int b) { if (b < a) a = b; }
int f[Max]; inline int min (int a, int b) { return a < b ? a : b; }
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, _s, s = INF, C, _C, L; read (N); rg int i, j;
for (i = ; i <= N; ++ i) read (a[i]), read (b[i]);
for (i = ; i <= ; ++ i)
{
_s = , C = , _C = ;
for (j = ; j <= N; ++ j)
if (b[j] <= i && (a[j] <= b[j] || a[j] > i)) _s += a[j];
else if (a[j] > i && b[j] > i) goto Here;
else if (b[j] > i) { ++ C; _s += b[j]; }
else f[++ _C] = a[j] - b[j], _s += a[j];
std :: sort (f + , f + _C + , Comp );
for (j = , L = min (N / - C, _C); j <= L; ++ j) _s -= f[j];
cmin (s, _s * i);
Here : continue;
}
printf ("%d", s); return ;
}
T3
/*
T3
预处理出没有修改的答案
观察结论判断答案
*/
#include <cstdio>
#include <iostream>
#include <cmath>
#define rg register
#define Max 200001
int a[][Max], N, M, P, _p, v, r; bool F;
std :: string Name = "xor", _I = ".in", _O = ".out";
inline void read (int &N)
{
rg char c = getchar ();
for (N = ; !isdigit (c); c = getchar ());
for (; isdigit (c); N = N * + c - '', c = getchar ());
}
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
read (N), read(M); int L = pow (, N); rg int i, j, z;
for (i = ; i <= L; ++ i) read (a[N][i]);
for (i = N - ; i >= ; -- i)
{
int l = pow (, i);
if ((N - i) % )
for (j = ; j <= l; ++ j)
a[i][j] = a[i + ][(j << ) - ]|a[i + ][(j << )];
else
for (j = ; j <= l; ++ j)
a[i][j]=a[i + ][(j << ) - ] ^ a[i + ][(j << )];
}
for (z = ; z <= M; ++ z)
{
F = false; read(P); read(r); a[N][P] = r;
if (P % ) _p = P + ; else _p = P, -- P;
for (i = N - ; i >= ; -- i)
{
if ((N - i) % )
{
v = a[i + ][P] | a[i + ][_p];
if (v == a[i][(P >> ) + (P - ((P >> ) << ))])
{ printf ("%d\n", a[][]); F = true; break; }
a[i][(P >> ) + (P - ((P >> ) << ))] = v;
P = (P >> ) + (P - ((P >> ) << ));
if (P % ) _p = P + ; else _p = P, -- P;
}
else
{
v = a[i + ][P] ^ a[i + ][_p];
if (v == a[i][(P >> ) + (P - ((P >> ) << ))])
{ printf ("%d\n", a[][]); F = true; break; }
a[i][(P >> ) + (P - ((P >> ) << ))] = v;
P = (P >> ) + (P - ((P >> ) << ));
if (P % ) _p = P + ; else _p = P, -- P;
}
}
if(!F) printf ("%d\n", a[][]);
}
}
20171002
上午
70 + 100 + 0 = 170 = rank 10
T1
/*
T1
贪心
观察发现每次删最大的点更优
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long LL;
#define rg register
const int BUF = ; char Buf[BUF], *buf = Buf;
inline void read (int &n)
{
for (n = ; !isdigit (*buf); ++ buf);
for (; isdigit (*buf); n = n * + *buf - '', ++ buf);
}
#define Max 100005
std :: string Name = "god", _I = ".in", _O = ".out";
int C, _v[Max << ], _n[Max << ], list[Max], c[Max]; LL s[Max];
struct D { int id, c; bool operator < (const D &rhs) const { return this->c > rhs.c; } } p[Max];
inline void In (int u, int v)
{
_v[++ C] = v, _n[C] = list[u], list[u] = C; s[v] += c[u];
_v[++ C] = u, _n[C] = list[v], list[v] = C; s[u] += c[v];
}
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
fread (buf, , BUF, stdin);
int N, M, x, y; LL Answer = ; read (N), read (M); rg int i, j, n;
for (i = ; i <= N; ++ i) read (c[i]), p[i].id = i, p[i].c = c[i];
std :: sort (p + , p + + N);
for (i = ; i <= M; ++ i) read (x), read (y), In (x, y);
for (i = ; i <= N; ++ i)
{
Answer += s[n = p[i].id];
for (j = list[n]; j; j = _n[j]) s[_v[j]] -= c[n];
}
std :: cout << Answer; return ;
}
T2
/*
T2
模拟 构造
分多种情况考虑
注意不要忘记其他情况
比如正负号之类。。
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
std :: string Name = "bit", _I = ".in", _O = ".out";
#define Max 100005
#define pc putchar
inline int min (int a, int b) { return a < b ? a : b; }
char s[Max]; bool F = false;
#define rg register
inline void Print (bool t)
{
rg int i, j; int Len = strlen (s);
for (i = t ? : ; i < Len; ++ i) if (s[i] != '') break;
for (j = min (Len - , i); j < Len; ++ j) pc (s[j]);
pc ('\n'); exit ();
}
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
scanf ("%s", s); rg int i, j, Len = strlen (s), _s = , r;
if (s[] != '-')
{
for (i = Len - ; i >= ; -- i)
{
if (s[i] >= '' && _s >= )
{
s[i] = char (s[i] - ), _s = ;
for (j = i + ; j < Len; ++ j)
for (; _s && s[j] < ''; -- _s, s[j] = char (s[j] + ));
for (j = i + , r = ; j < Len; ++ j) r += s[j] - '';
for (j = i + ; j < Len; ++ j)
if (r >= ) s[j] = '', r -= ;
else s[j] = char (r + ''), r = ;
F = true; break;
}
_s += '' - s[i];
}
if (F) Print (false);
pc ('-');
for (i = Len - ; i >= ; -- i)
if (s[i] < '') { s[i] = char (s[i] + ), F = true; break; }
if (F) Print (false);
pc (''); Print (false);
}
F = false; pc ('-');
for (i = Len - ; i >= ; -- i)
if (s[i] < '') { s[i] = char (s[i] + ), F = true; break; }
if (F) Print (true);
pc (''), Print (true); return ;
}
T3
/*
T3
利用了归并排序的思想
预处理一下
*/
#include <cstdio>
#include <iostream>
#define Max 200005
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
#ifdef WIN32
#define PLL "%I64d"
#else
#define PLL "%lld"
#endif
std :: string Name = "pair", _I = ".in", _O = ".out";
typedef long long LL; LL _u[], _d[];
int a[Max], b[Max], c[Max]; bool is[];
void MergeUp (int n, int l, int r)
{
if (!n) return ; rg int m = l + r >> , i, j, k;
MergeUp (n - , l, m), MergeUp (n - , m + , r);
for (i = l, j = m + , k = l; i <= m && j <= r;)
if (a[i] <= a[j]) c[k ++] = a[i ++];
else _d[n] += (LL) m - i + , c[k ++] = a[j ++];
for (; i <= m; c[k ++] = a[i ++]);
for (; j <= r; c[k ++] = a[j ++]);
for (i = l; i <= r; ++ i) a[i] = c[i];
}
void MergeDown (int n, int l, int r)
{
if (!n) return ; rg int m = l + r >> , i, j, k;
MergeDown (n - , l, m), MergeDown (n - , m + , r);
for (i = l, j = m + , k = l; i <= m && j <= r;)
if (b[i] >= b[j]) c[k ++] = b[i ++];
else _u[n] += (LL) m - i + , c[k ++] = b[j ++];
for (; i <= m; c[k ++] = b[i ++]);
for (; j <= r; c[k ++] = b[j ++]);
for (i = l; i <= r; ++ i) b[i] = c[i];
}
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, L, Q, x; read (N); rg int i, j; LL s;
for (i = , L = ( << N); i <= L; ++ i) read (a[i]), b[i] = a[i];
MergeUp (N, , << N), MergeDown (N, , << N);
for (read (Q); Q; -- Q)
{
for (i = , read (x), s = ; i <= x; ++ i)
if (is[i]) s += _d[i], is[i] = false;
else s += _u[i], is[i] = true;
for (i = x + ; i <= N; ++ i)
if (is[i]) s += _u[i]; else s += _d[i];
printf (PLL"\n", s);
}
return ;
}
下午
50 + 70 + 100 = 220 = rank 3
T1
/*
T1
枚举左端点
计算右端点
*/
#include <cstdio>
#include <iostream>
#define Max 100008
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
typedef long long LL; LL s[Max];
std :: string Name = "max", _I = ".in", _O = ".out";
LL lt[Max], rt[Max], sm[Max], Mx;
LL lx[Max], ly[Max], Answer; int X, Y;
inline void ch (LL &x, LL y, LL z, int p, int _p, int i)
{ if (y < z) x = z, lx[i] = _p; else x = y, lx[i] = p; }
void hc (LL &x, LL y, LL z, int p, int _p, int i)
{ if (y < z) x = z, ly[i] = _p; else x = y, ly[i] = p; }
void cc (LL &x, LL y, int i) { if (x < y) x = y, X = lx[i - ], Y = ly[i]; }
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, K, x, res; read (N), read (K); rg int i, j;
for (i = ; i <= N; ++ i)
read (x), s[i] = s[i - ] + x, Answer += x;
for (i = ; i <= N; ++ i) sm[i] = Answer - s[i - ];
for (i = ; i <= K; ++ i) lt[i] = s[i], lx[i] = ;
for (i = N; i >= N - K + ; -- i) rt[i] = sm[i], ly[i] = i;
for (i = K + ; i <= N; ++ i)
ch (lt[i], lt[i - ], s[i] - s[i - K], lx[i - ], i - K + , i);
for (i = N - K; i >= ; -- i)
hc (rt[i], rt[i + ], sm[i] - sm[i + K], ly[i + ], i, i);
for (i = K + ; i <= N - K + ; ++ i) cc (Mx, lt[i - ] + rt[i], i);
std :: cout << X << " " << Y; return ;
}
T2
/*
T2
开个桶
记录下合法的所有情况
然后挨个判断，计算
*/
#include <cstdio>
#include <iostream>
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
#define Max 100000007
#define _Max 5005
typedef long long LL; int f[Max], v[Max / ], _v[Max / ]; LL s;
int A, B, C, D, N, a[_Max], aa[_Max], b[_Max], c[_Max], d[_Max];
std :: string Name = "eat", _I = ".in", _O = ".out";
inline void cmax (int &a, int b) { if (b > a) a = b; }
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
read (N), read (A), read (B), read (C), read (D); rg int i, j;
for (i = ; i <= A; ++ i) read (a[i]);
for (i = ; i <= B; ++ i) read (b[i]);
int Maxn = , T = , _T = ;
for (i = ; i <= A; ++ i)
for (j = ; j <= B; ++ j)
if (a[i] + b[j] <= N)
++ f[a[i] + b[j]], cmax (Maxn, a[i] + b[j]);
for (i = ; i <= Maxn; ++ i)
for (; f[i]; -- f[i], v[++ T] = i);
for (i = ; i <= C; ++ i) read (c[i]);
for (i = ; i <= D; ++ i) read (d[i]);
for (Maxn = , i = ; i <= C; ++ i)
for (j = ; j <= D; ++ j)
if (c[i] + d[j] <= N)
++ f[c[i] + d[j]], cmax (Maxn, c[i] + d[j]);
for (i = ; i <= Maxn; ++ i)
for (; f[i]; -- f[i], _v[++ _T] = i);
for (i = _T; i >= ; -- i) if (v[] + _v[i] <= N) break;
for (j = ; j <= T; ++ j)
for (s += i; i && v[j + ] + _v[i] > N; -- i);
std :: cout << s; return ;
}
T3
/*
T3
数位dp
f[i][j][k][l][t]表示n的前i位，分完后的余数为j，
第1/2/3个人的第i位能否随便填的方案数
转移时枚举每个人克分到的数目
注意判断进位
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#define rg register
#define Mod 12345647
#define Max 10005
std :: string Name = "candy", _I = ".in", _O = ".out";
int f[Max][][][][], a[Max], b[Max]; char n[Max], x[Max];
inline void Acalc (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
scanf ("%s", n), scanf ("%s", x); int L1 = strlen (n), L2 = strlen (x);
int i, j, k, l, t, I, J, K, L, T;
for (i = ; i < L1; ++ i) a[i + ] = n[i] - '';
for (i = ; i < L2; ++ i) b[i + L1 - L2 + ] = x[i] - '';
f[][][][][] = ; rg int p, q, e; int s = ;
for (i = ; i < L1; ++ i)
for (j = ; j <= ; ++ j)
for (k = ; k <= ; ++ k)
for (l = ; l <= ; ++ l)
for (t = ; t <= ; ++ t)
if (f[i][j][k][l][t])
for (p = ; p <= ; ++ p)
if (p != )
for (q = ; q <= ; ++ q)
if (q != )
for (e = ; e <= ; ++ e)
if (e != )
{
I = i + , J = j * + a[i + ] - p - q - e;
if (J > || J < ) continue;
if (k == && p < b[i + ]) continue;
K = (k || p > b[i + ]);
if (l == && q < b[i + ]) continue;
L = (l || q > b[i + ]);
if (t == && e < b[i + ]) continue;
T = (t || e > b[i + ]);
Acalc (f[I][J][K][L][T], f[i][j][k][l][t]);
}
for (i = ; i <= ; ++ i)
for (j = ; j <= ; ++ j)
for (k = ; k <= ; ++ k) Acalc (s, f[L1][][i][j][k]);
printf ("%d", s); return ;
}
20171003
上午
100 + 100 + 10 = 210 = rank 1
T1
/*
T1
set 判下重就好
*/
#include <cstdio>
#include <iostream>
#include <set>
#include <algorithm>
#define rg register
using std :: string;
string Name = "a", _I = ".in", _O = ".out"; std :: set <string> s;
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, Len; scanf ("%d", &N); rg int i, j; string r;
for (i = ; i <= N; ++ i)
{ std :: cin >> r; std :: sort (r.begin (), r.end ()), s.insert (r); }
printf ("%d", s.size ());
fclose (stdin); fclose (stdout); return ;
}
T2
/*
T2
分两种情况讨论一下
设三角形的边长为a, b, c
1.b == c
2.b != c
第一种情况可以直接求得
而第二种情况需要组合数学与插板法来推一下
*/
#include <cstdio>
#include <iostream>
#include <cmath>
#define Max 1000010
#define rg register
typedef long long LL;
const int Mod = (int)1e9 + ; int f[Max], y[Max];
inline void Sub (int &a, int b) { if (a >= b) a -= b; }
inline void J (int &a, int b) { if (a < ) a += b; }
std :: string Name = "b", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N; f[] = ; LL s = ;
rg int i, j, r; scanf ("%d", &N);
for (i = ; i < Max; ++ i)
{
f[i] = f[i - ] + floor ((i - ) / .) - ceil (i / .) + ;
if ((i & ) == ) f[i] -= floor ((i / ) / .);
Sub (f[i], Mod), J (f[i], Mod);
}
for (i = , y[] = , y[] = ; i < Max; ++ i)
{
y[i] = (y[i - ] << ), Sub (y[i], Mod);
for (j = ; i * j < Max; ++ j) f[r = i * j] -= f[i], J (f[r], Mod);
}
for (i = ; i * i <= N; ++ i)
if (N % i == )
{
s = (s + (LL) f[i] * y[N / i]) % Mod;
if (i * i != N) s = (s + (LL) f[N / i] * y[i]) % Mod;
}
std :: cout << (s + Mod) % Mod; return ;
}
T3
/*
T3
容斥原理
从左下角开始
像一个倒L形一样计算
一层一层更新答案
*/
#include <cstdio>
#include <iostream>
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
inline int max (int a, int b) { return a > b ? a : b; }
const int mo = 1e9 + ; typedef long long LL;
std :: string Name = "c", _I = ".in", _O = ".out";
#define Max 10050
int a[Max], b[Max], c[Max / ][Max / ];
inline int Pow (int x, int b)
{
int r = ;
for (; b; x = 1LL * x * x % mo, b >>= )
if (b & ) r = 1LL * r * x % mo;
return r;
}
inline void Acalc (int &a, int b) { a += b; if (a >= mo) a -= mo; }
int Calc (int N, int M, int n, int m, int h)
{
rg int i, j, r; int s = ;
for (i = ; i <= n; ++ i)
for (j = ; j <= m; ++ j)
{
r = 1LL * Pow (h, N * M - (N - i) * (M - j))
* Pow (h + , (N - i) * (M - j) - (N - n)
* (M - m)) % mo * c[n][i] % mo
* c[m][j] % mo;
if ((i + j) & ) s = ((s - r) % mo + mo) % mo;
else Acalc (s, r);
}
return s;
}
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, M, x, y, L = ; LL s = ; read (N), read (M); rg int i, j, pn, pm;
for (i = ; i <= N; ++ i) read (x), ++ a[x];
for (i = ; i <= M; ++ i) read (x), ++ b[x];
for (i = , L = max (N, M); i <= L; ++ i) c[i][] = c[i][i] = ;
for (i = ; i <= L; ++ i)
for (j = ; j < L; ++ j) c[i][j] = (c[i - ][j - ] + c[i - ][j]) % mo;
for (i = (Max - ), pn = pm = ; i >= ; -- i)
if (a[i] || b[i])
pn += a[i], pm += b[i], s = 1LL * s * Calc (pn, pm, a[i], b[i], i) % mo;
std :: cout << s; return ;
}
下午
200 + 36 + 200 = 436 = rank 6
T1
/*
T1
栈模拟一下就好
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#define Max 100005
char s[Max], a[Max];
#define rg register
std :: string Name = "a", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
gets (s); int Len = strlen (s), k = ; a[] = s[]; rg int i;
if (Len == ) return printf ("OK"), ;
for (i = ; i < Len ; ++ i)
if (s[i] - a[k] == || a[k] == '(' && s[i]==')') -- k;
else a[++ k] = s[i];
if (k) printf("Wrong"); else printf("OK");
fclose (stdin); fclose (stdout); return ;
}
T2
/*
T2
三分
将棺材下部分看做一条直线
求斜率，求距离
三分就好
*/
#include <cstdio>
#include <iostream>
#include <cmath>
#define rg register
typedef double flo; int a, b, l;
std :: string Name = "b", _I = ".in", _O = ".out";
inline flo C (flo n)
{
flo p = sqrt (l * l - n * n);
return (a * n + b * p < n * p) ? -1e+ : (a * n + b * p - n * p) / l;
}
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
scanf ("%d%d%d", &a, &b, &l);
if (a >= l && b >= l) return printf ("%d.0000000", l), ;
if (a >= l) return printf ("%d.0000000", b), ;
if (b >= l) return printf ("%d.0000000", a), ;
flo _l = 0.0, _r = l, m1, m2;
for (rg int i = ; i <= ; ++ i)
{
m1 = _l + (_r - _l) / 3.0, m2 = _r - (_r - _l) / 3.0;
if (C (m1) < 0.0 || C (m2) < 0.0) return printf ("My poor head =("), ;
if (C (m1) < C (m2)) _r = m2; else _l = m1;
}
printf ("%.7lf", C (_r));
fclose (stdin); fclose (stdout); return ;
}
T3
/*
T3
贪心
将原树尽可能分成多的长链
Dfs一遍就好
*/
#include <iostream>
#include <cstdio>
#define Max 100009
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
struct E { E *n; int v; } *list[Max], pool[Max << ], *Ta = pool; int s = ;
int Dfs (int n, int F)
{
rg int v, i, r = ;
for (E *e = list[n]; e; e = e->n)
if ((v = e->v) != F) r += Dfs (v, n);
if (r > && F == -) s += r - ;
else if (r > ) { s += r - ; return ; } return ;
}
inline void In (int u, int v)
{
++ Ta, Ta->v = v, Ta->n = list[u], list[u] = Ta;
++ Ta, Ta->v = u, Ta->n = list[v], list[v] = Ta;
}
std :: string Name = "c", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, i, x, y; read (N);
for(i = ; i < N; i ++) read (x), read (y), In (x, y);
Dfs (, -); printf("%d", s * - ); return ;
}
20171004
上午
0 + 100 + 20 = 120 = rank 4
T1
#include <iostream>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <cstdio>
using std :: string;
string Name = "a", _I = ".in", _O = ".out";
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
using std :: cout;
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, L, _s, p; read (N); rg int i; string s; bool F;
for (; std :: cin >> s; )
{
for (L = s.size (), _s = , p = , i = , F = false; i < L; ++ i)
if (s[i] == '') ++ p, _s += i + ;
if (L == N)
{
if (_s % (N + ) == ) std :: cout << s << '\n';
else
{
for (i = ; i < L; ++ i)
{
if (s[i] == '') continue;
if ((_s - (i + )) % (N + ) == )
{ s[i] = '', std :: cout << s << '\n', F = true; break; }
}
if (!F) puts ("-1");
}
}
else if (L == N + )
{
for (i = ; i < L; ++ i)
{
if(s[i]=='')
{
-- p;
if((_s - (i + ) - p) % (N + ) == )
{ s.erase (i, ); std :: cout << s << '\n', F = true; break; }
}
else if ((_s - p) % (N + ) == )
{ s.erase (i, ), std :: cout << s << '\n', F = true; break; }
}
if (!F) puts ("-1");
}
else if (L == N - )
{
for (i = ; i < L; ++ i)
{
if((_s + p) % (N + ) == )
{ s.insert (i, , ''), cout << s << '\n', F = true; break; }
else if((_s + (i + ) + p) % (N + ) == )
{ s.insert (i, , ''), cout << s << '\n', F = true; break; }
if (s[i] == '') -- p;
}
if (!F)
{
if (_s % (N + ) == )
s = s + '', cout << s << '\n', F = true;
else if ((_s + L + ) % (N + ) == )
s = s + '', cout << s << '\n', F = true;
}
if (!F) puts ("-1");
}
else puts ("-1");
}
return ;
}
T2
#include <cstdio>
#include <cstring>
#include <iostream>
typedef long long LL;
#define Max 103
LL fac[Max], f[Max * Max / ][Max], inv[Max];
#define Mod 905229641
int m; LL n,s;
#define rg register
LL fast (LL a, LL p)
{
LL res = ;
for (; p; p >>= , a = a * a % Mod)
if (p & ) res = res * a % Mod;
return res;
}
LL c (LL N, LL M)
{
if (M == ) return ; LL res = ;
for (LL i = N - M + ; i <= N; i ++) res = res * (i % Mod) % Mod;
return res * inv[M] % Mod;
}
std :: string Name = "b", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
f[][] = f[][] = ;std :: cin >> n >> m;
fac[] = ; rg int i, j, k;
for (i = ; i <= m; i ++) fac[i] = fac[i - ] * i % Mod;
inv[m] = fast (fac[m], Mod - );
for (i = m - ; i >= ; i --) inv[i] = inv[i + ] * (i + ) % Mod;
for (k = ; k < m - ; ++ k)
{
int r = k * (k + ) / ;
for (i = r; i >= ; -- i)
for (j = k + ; j >= ; -- j)
if (f[i][j]) f[i + k + ][j + ] = (f[i + k + ][j + ] + f[i][j]) % Mod;
}
int r = m * (m - ) / ;
for (LL i = ; i <= r; ++ i)
if ((n - i) % m == )
{
rg LL _c = (n - i) / m;
for (LL j = ; j <= m; ++ j)
if (f[i][j]) s = (s + f[i][j] * c (_c + j - ,j - ) % Mod * fac[j] % Mod) % Mod;
}
std :: cout << s;
}
T3
下午
200 + 100 + 0 = 300 = rank 5
T1
#include <cstdio>
#include <iostream>
#include <cmath>
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
#define Max 40000000
int c[Max]; typedef long long LL;
std :: string Name = "a", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, t, x; read (N); rg int i, j, L; LL s = ;
for (i = ; i <= N; ++ i)
{
read (t), read (x);
if (t == )
{
for (j = ; j * j < x; ++ j)
if (x % j == ) ++ c[j], ++ c[x / j];
if (j * j == x) ++ c[j];
}
else s ^= c[x];
}
std :: cout << s; fclose (stdin); fclose (stdout); return ;
}
T2
#include <cstdio>
#include <iostream>
typedef long long LL;
#define rg register
inline void read (LL &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
#define Max 300005
struct E { int v, c; E *n; } *list[Max], pool[Max << ], *Ta = pool;
inline void In (int u, int v, int c)
{ ++ Ta, Ta->v = v, Ta->n = list[u], list[u] = Ta, Ta->c = c; }
int c[Max]; LL f[Max], v[Max], s;
void Dfs (int n, int F, int _l)
{
LL r = ; int V; f[n] = v[n], c[n] = ; bool _F = false; E *e;
for (e = list[n]; e; e = e->n)
if ((V = e->v) != F)
{
Dfs (V, n, e->c);
if (e->c != _l)
_F = true, c[n] += c[V], f[n] += c[V] * v[n] + f[V];
r += c[V] * v[n] + f[V];
}
s += r; if (!_F) return ; E *a;
for (e = list[n]; e; e = e->n)
if ((V = e->v) != F)
for (a = e; a; a = a->n)
if (a->v != F && e->c != a->c)
s += f[V] * c[a->v] + f[a->v] * c[V] + v[n] * c[a->v] * c[V];
}
std :: string Name = "b", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
LL N, x, y, z; read (N); rg int i;
for (i = ; i <= N; ++ i) read (v[i]);
for(i = ; i < N; ++ i)
{
read (x), read (y), read (z);
In (x, y, z), In (y, x, z);
}
Dfs (, , ); std :: cout << s; return ;
}
T3
/*
233333
高级cheat
*/
#include <cstdio>
#include <ctime>
#include <cstdlib>
int main (int argc, char *argv[])
{
freopen ("data.txt", "r", stdin);
int N;
if (scanf ("%d", &N) == EOF)
{
fclose (stdin);
freopen ("data.txt", "w", stdout);
putchar ('');
fclose (stdout);
freopen ("c.out", "w", stdout);
putchar ('');
fclose (stdout);
}
else
{
fclose (stdin);
freopen ("data.txt", "w", stdout);
if (N == )
{
printf ("%d", ++ N);
fclose (stdout);
freopen ("c.out", "w", stdout);
putchar ('');
fclose (stdout);
}
else if (N == )
{
printf ("%d", ++ N);
fclose (stdout);
freopen ("c.out", "w", stdout);
printf ("");
fclose (stdout);
}
else if (N == )
{
printf ("%d", ++ N);
fclose (stdout);
freopen ("c.out", "w", stdout);
printf ("");
fclose (stdout);
}
else if (N == )
{
printf ("%d", ++ N);
fclose (stdout);
freopen ("c.out", "w", stdout);
printf ("");
fclose (stdout);
}
else if (N == )
{
printf ("%d", ++ N);
fclose (stdout);
freopen ("c.out", "w", stdout);
printf ("");
fclose (stdout);
}
else if (N == )
{
printf ("%d", ++ N);
fclose (stdout);
freopen ("c.out", "w", stdout);
printf ("");
fclose (stdout);
}
else if (N == )
{
printf ("%d", ++ N);
fclose (stdout);
freopen ("c.out", "w", stdout);
printf ("");
fclose (stdout);
}
else if (N == )
{
printf ("%d", ++ N);
fclose (stdout);
freopen ("c.out", "w", stdout);
printf ("");
fclose (stdout);
}
else
{
printf ("%d", ++ N);
fclose (stdout);
freopen ("c.out", "w", stdout);
printf ("");
fclose (stdout);
}
}
return ;
}
20171005上
上午
0 + 60 + 60 = 120 = rank 1
T1
/*
T1
行列式
找规律
*/
#include <cstdio>
#include <iostream>
#define rg register
inline void read (int &n)
{
rg char c = getchar (); bool temp = false;
for (n = ; !isdigit (c); c = getchar ()) if (c == '-') temp = true;
for (; isdigit (c); n = n * + c - '', c = getchar ());
if (temp) n = -n;
}
inline int abs (int x) { return x < ? -x : x; }
int Gcd (int a, int b) { return !b ? a : Gcd (b, a % b); }
bool J ()
{
int N, M, x = , y; rg int i;
read (N), read (M);
for (i = ; i <= N; ++ i) read (y), x = Gcd (x, abs (y));
if (N == ) return y == M;
if (!x) return !M; return !(abs (M) % x);
}
std :: string Name = "det", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int T; read (T);
for (; T; -- T) printf (J () ? "Y\n" : "N\n");
return ;
}
T2
/*
T2
分治
*/
#include <iostream>
#include <cstdio>
typedef long long LL; LL mo;
#define rg register
inline void read (LL &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
struct D { LL x, y; D (LL a = , LL b = ) : x (a), y (b) {} };
std :: string Name = "seq", _I = ".in", _O = ".out";
#ifdef WIN32
#define PLL "%I64d"
#else
#define PLL "%lld"
#endif
inline void cmax (LL &a, LL b) { if (b > a) a = b; }
inline void cmin (LL &a, LL b) { if (b < a) a = b; }
D Dfs (LL n, LL l, LL r, LL x, LL y)
{
if (x > n || l > r) return D (, );
if (l == && r == n)
{
cmax (x, 1LL), cmin (y, n); LL s;
if ((x + y) % == ) s = ((x + y) / ) % mo * ((y - x + ) % mo) % mo;
else s = ((x + y) % mo) * ((y - x + ) / % mo) % mo;
return D (s % mo, y - x + );
}
LL m = (n + ) >> ; D t, p;
if (r <= m)
{ t = Dfs (m, l, r, x / + , (y + ) / ); return D ((t.x * - t.y) % mo, t.y); }
else if (l > m)
{ t = Dfs (n - m, l - m, r - m, (x + ) / , y / ); return D (t.x * % mo, t.y); }
else
{
t = Dfs (m, l, m, x / + , (y + ) / );
p = Dfs (n - m, , r - m, (x + ) / , y / );
return D ((t.x * - t.y + p.x * ) % mo, (t.y + p.y) % mo);
}
}
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
LL N, M, l, r, u, v; read (N), read (M), read (mo); rg int i;
for (i = ; i <= M; ++ i)
{
read (l), read (r), read (u), read (v);
printf (PLL"\n", (Dfs (N, l, r, u, v).x + mo) % mo);
}
return ;
}
T3
/*
T3
树形dp
*/
#include <iostream>
#include <cstdio>
#define Max 100010
typedef long long LL;
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
struct E { E *n; int v; } *list[Max], pool[Max << ], *Ta = pool;
inline void In (int u, int v)
{ ++ Ta, Ta->v = v, Ta->n = list[u], list[u] = Ta; }
int lca[Max][], _n[Max], c[Max][], f[Max][], _s[Max]; LL s;
void Dfs_1 (int n, int F)
{
lca[n][] = F, _s[n] = ; rg int i, v;
for (i = ; i <= ; ++ i)
lca[n][i] = lca[lca[n][i - ]][i - ];
for (E *e = list[n]; e; e = e->n)
if ((v = e->v) != F) Dfs_1 (v, n), _s[n] += _s[v];
}
void Dfs (int n, int F)
{
rg int i, v, j;
for (E *e = list[n]; e; e = e->n)
if ((v = e->v) != F) _n[n] = v, Dfs (v, n);
for (i = ; i <= ; ++ i)
s += _s[v = lca[n][i]] - _s[_n[v]], ++ c[v][i], ++ f[v][i];
for (i = ; i <= ; ++ i)
for (j = ; j < i; ++ j)
s += LL (c[n][i] + f[n][i]) * LL (_s[v = lca[n][j]] - _s[_n[v]]), c[v][j] += c[n][i], f[v][j] += f[n][i] + c[n][i];
}
std :: string Name = "bitcount", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N; read (N); int x, y; rg int i, j;
for (i = ; i < N; ++ i)
read (x), read (y), In (x, y), In(y, x);
Dfs_1 (, ); _s[] = _s[], _n[] = , Dfs (, );
std :: cout << s; return ;
}
下午
0 + 60 + 0 = 60 = rank 26
T1
T2
T3
20171006
上午
100 + 50 + 0 = 150 = rank 14
T1
/*
简直智障
脑子抽了写个双向链表。。。
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#define rg register
#define Max 10009
char l[Max];
int _n[Max], _l[Max];
std :: string Name = "kakutani", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, Len, C; scanf ("%d", &N); rg int i, j;
for (; N; -- N)
{
scanf ("%s", l + ); Len = strlen (l + ); _n[] = ; C = Len;
for (i = ; i <= Len + ; ++ i) _n[i] = i + , _l[i] = i - ;
for (i = ; i <= Len; i = _n[i])
for (; l[i] == '' || l[i] == '' || (l[_l[i]] == '' && l[i] == '') || (l[_n[i]] == '' && l[i] == ''); )
{
for (; l[i] == '';)
l[i] = l[_n[i]], _n[i] = _n[_n[i]], _l[_n[i]] = i, _n[_l[i]] = i, -- C;
for (; l[i] == '';)
l[i] = l[_n[i]], _n[i] = _n[_n[i]], _l[_n[i]] = i, _n[_l[i]] = i, -- C;
for (; l[_n[i]] == '' && l[i] == ''; )
C -= , l[i] = l[_l[i]], _l[i] = _l[_l[i]], _n[_l[i]] = i, _n[i] = _n[_n[i]], _l[_n[i]] = i;
for (; l[_l[i]] == '' && l[i] == ''; )
C -= , l[i] = l[_n[i]], _n[i] = _n[_n[i]], _l[_n[i]] = i, _l[i] = _l[_l[i]], _n[_l[i]] = i;
}
if (!C) { puts (""); continue; }
else for (i = , C = ; i <= Len; i = _n[i]) if (l[i] != '\0') ++ C, putchar (l[i]);
putchar ('\n');
}
return ;
}
T2
T3
下午
100 + 0 + 20 = 120 = rank 7
T1
T2
T3
20171007
上午
100 + 30 + 20 = 150 = rank 17
T1
#include <cstdio>
#include <iostream>
#include <algorithm>
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
#define Max 100009
int c[Max];
std :: string Name = "del", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, K; read (N), read (K); rg int i, s;
for (i = ; i <= N; ++ i) read (c[i]);
std :: sort (c + , c + + N);
s = std :: unique (c + , c + + N) - c - ; s = N - s;
if (K <= s) printf ("%d", N - s); else printf ("%d", N - K);
return ;
}
T2
T3
/*
T2
读入优化考场忘判负数挂成20的我也是很棒棒
*/
#include <iostream>
#include <cstdio>
typedef double flo;
#define Max 15
int K, N, x, v[Max], s[Max];
#define rg register
flo f[( << Max)][Max * ]; bool is[( << Max)][Max * ];
inline flo max (flo a, flo b) { return a > b ? a : b; }
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
flo Calc (int n, int d)
{
if (is[n][d] || d > K) return f[n][d];
is[n][d] = ; flo r = Calc (n, d + );
for (rg int i = ; i < N; ++ i)
if ((s[i] & n) == s[i]) f[n][d] += max (r, Calc (n | ( << i), d + ) + v[i]);
else f[n][d] += r;
return f[n][d] /= N;
}
std :: string Name = "bonus", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
read (K), read (N); rg int i;
for (i = ; i < N; ++ i)
for (read (v[i]); scanf ("%d", &x) && x; s[i] |= ( << (x - )));
printf ("%.6lf\n", Calc (, ));
}
下午
100 + 100 + 100 = 300 = rank 1
T1
/*
T1
找出花色不同的连续的最长的牌
记其中牌的数量为s
那么答案即为n - s
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define rg register
#define Max 100005
struct D
{
int x, y;
bool operator < (const D &A) const { return A.x == x ? y < A.y : x < A.x; }
bool operator == (const D &A) const { return x == A.x && y == A.y; }
} a[Max];
inline void read (int &n)
{
rg char c = getchar (); bool temp = false;
for (n = ; !isdigit (c); c = getchar ()) if (c == '-') temp = true;
for (; isdigit (c); n = n * + c - '', c = getchar ());
if (temp) n = -n;
}
inline void cmax (int &a, int b) { if (b > a) a = b; }
std :: string Name = "card", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, M, r = , s = ; read (N); rg int i, j, k, l;
for (i = ; i <= N; ++ i) read (a[i].x), read (a[i].y);
std :: sort (a + , a + N + ); M = std :: unique (a + , a + N + ) - a - ;
for (i = , j = ; i <= M; ++ i)
if (a[i].x != a[i - ].x)
{
for (r = , k = j, l = j; k <= i - ; ++ k)
{
for (; l < i - && a[l + ].y - a[k].y < N; ++ l);
cmax (r, l - k + );
}
cmax (s, r), j = i;
}
for (r = , k = j, l = j; k <= i - ; ++ k)
{
for (; l < i - && a[l + ].y - a[k].y < N; ++ l);
cmax (r, l - k + );
}
cmax (s, r); std :: cout << N - s; return ;
}
T2
/*
T2
记f[x]为x这个数字所表示的子集上次出现的位置
那么暴力枚举读入的数的子集
判断计算更新即可
*/
#include <cstdio>
#include <iostream>
#define rg register
inline void read (int &n)
{
rg char c = getchar ();
for (n = ; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * + c - '', c = getchar ());
}
#define Max 100010
int f[Max];
std :: string Name = "test", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
int N, x, y, r; read (N); rg int i, s;
for (i = ; i <= N; ++ i)
{
read (x), read (y); r = x, s = ;
if (f[r] < i - y) ++ s; f[r] = i, r = x & (r - );
for (; r; f[r] = i, r = x & (r - )) if (f[r] < i - y) ++ s;
printf ("%d\n", s);
}
return ;
}
T3
BZOJ 1179: [Apio2009]Atm
#include <cstdio>
#include <stack>
#include <queue>
#include <iostream>#define Max 500900inline int max (int a, int b)
{
return a > b ? a : b;
}inline int min (int a, int b)
{
return a < b ? a : b;
}void read (int &now)
{
now = ;
register char word = getchar ();
while (word > '' || word < '')
word = getchar ();
while (word >= '' && word <= '')
{
now = now * + word - '';
word = getchar ();
}
}struct Edge_Type
{
struct Edge
{
int to;
int next;
int dis;
}
edge[Max]; int Edge_Count;
int edge_list[Max]; void Add_Edge (int from, int to)
{
Edge_Count++;
edge[Edge_Count].to = to;
edge[Edge_Count].next = edge_list[from];
edge_list[from] = Edge_Count;
}
};Edge_Type Graph_1;Edge_Type Graph;int point_dis[Max];
int value[Max];int N, M;struct Tarjan_Type
{ std :: stack <int> Stack; int number[Max];
int lowlink[Max];
int Scc_Count; int Count; int scc_number[Max]; void Tarjan_ (int N)
{
for (int i = ; i <= N; i++)
if (!number[i])
Dfs (i);
} void Dfs (int now)
{
Count++;
number[now] = Count;
lowlink[now] = Count;
Stack.push (now);
for (int i = Graph_1.edge_list[now]; i; i = Graph_1.edge[i].next)
if (!number[Graph_1.edge[i].to])
{
Dfs (Graph_1.edge[i].to);
lowlink[now] = min (lowlink[now], lowlink[Graph_1.edge[i].to]);
}
else if (!scc_number[Graph_1.edge[i].to])
lowlink[now] = min (lowlink[now], number[Graph_1.edge[i].to]);
if (lowlink[now] == number[now])
{
Scc_Count++;
int res = now + ;
while (res != now)
{
res = Stack.top ();
Stack.pop ();
scc_number[res] = Scc_Count;
point_dis[Scc_Count] += value[res];
}
}
} void Narrow_Point ()
{
for (int now = ; now <= N; now++)
for (int i = Graph_1.edge_list[now]; i; i = Graph_1.edge[i].next)
if (scc_number[now] != scc_number[Graph_1.edge[i].to])
Graph.Add_Edge (scc_number[now], scc_number[Graph_1.edge[i].to]);
}
};Tarjan_Type Make;struct Spfa_Type
{
int distance[Max]; std :: queue <int> Queue;
bool visit[Max]; int S; void Do_Spfa (int S)
{
Queue.push (S);
visit[S] = true;
int now;
distance[S] = point_dis[S];
while (!Queue.empty ())
{
now = Queue.front ();
Queue.pop ();
visit[now] = false;
for (int i = Graph.edge_list[now]; i; i = Graph.edge[i].next)
if (distance[Graph.edge[i].to] < distance[now] + point_dis[Graph.edge[i].to])
{
distance[Graph.edge[i].to] = distance[now] + point_dis[Graph.edge[i].to];
if (!visit[Graph.edge[i].to])
{
Queue.push (Graph.edge[i].to);
visit[Graph.edge[i].to] = true;
}
}
}
}
};Spfa_Type Spfa;
int S, P;
std :: string Name = "save", _I = ".in", _O = ".out";
int main (int argc, char *argv[])
{
freopen ((Name + _I).c_str (), "r", stdin);
freopen ((Name + _O).c_str (), "w", stdout);
read (N);
read (M);
int x, y;
for (int i = ; i <= M; i++)
{
read (x);
read (y);
Graph_1.Add_Edge (x, y);
}
for (int i = ; i <= N; i++)
read (value[i]);
Make.Tarjan_ (N);
Make.Narrow_Point ();
read (S);
read (P);
Spfa.Do_Spfa (Make.scc_number[S]);
int Answer = ;
for (int i = ; i <= P; i++)
{
read (x);
Answer = max (Answer, Spfa.distance[Make.scc_number[x]]);
}
printf ("%d", Answer);
return ;
}
