CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Ticket
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
double ans, tot, a;
int n;
scanf("%d", &n);
while (n--)
{
scanf("%lf", &a);
if (tot < 100)
{
tot += a;
}
else if (tot >= 100 && tot < 150)
{
tot += 0.8 * a;
}
else if (tot >= 150 && tot < 400)
{
tot += 0.5 * a;
}
else
tot += a;
}
printf("%.2lf\n", tot);
}
Gcd
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; } //??a+b<2*M,??????,????????
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); } //??a?b??????????????
// ll mul(ll a, ll b) const { return add(a * b, M); }
ll inv(ll a) const { return pow(a, M - 2); } //??M???,??return pow(a, phi(M) - 1);
ll pow(ll a, ll b) const
{
ll r = 1;
/*
if (b < 0)
b = -b, a = inv(a);
*/
for (a = add(a, M); b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
ll mul(ll a, ll b) const { return add(a * b, -M * (ll)((long double)a / M * b)); } //long double ????16~18?,???????!
/*ll mul(ll a, ll b) const //Head??,???????????,??a*b???ll??a*b%M,??a<M?b<M,?????????
{
ll c = a / SM, d = b / SM;
a %= SM, b %= SM;
ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
}
ll mul(ll a, ll b) const //???
{
ll r = 0;
for (a %= M; b; b >>= 1, qadd(a, a))
if (b & 1)
qadd(r, a);
return r;
}
ll inv(ll a) const //?m?a?????,?????-1(m????a??0????)
{
ll x, y, d = gcd(a, M, x, y);
return d == 1 ? add(x, M) : -1;
}
vector<ll> sol(ll a, ll b) const //?????,??ax=b(mod M)???????
{
vector<ll> ans;
ll x, y, d = gcd(a, M, x, y);
if (b % d)
return ans;
ans.push_back(mul((b / d) % (M / d), x));
for (ll i = 1; i < d; ++i)
ans.push_back(add(ans.back(), M / d));
return ans;
}
ll log(ll a, ll b) const
{
unordered_map<ll, ll> x;
for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
if (!x.count(e))
x[e] = i;
for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
if (x.count(b))
return i * SM + x[b];
return -1;
}
*/
};
struct PollardRho
{
bool isPrime(ll n, int S = 12) //MillerRabin????,S?????,??S??????,S=12???unsigned long long?????;n<2???
{
static ll d, u, t, p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (d = n - 1; !(d & 1);)
d >>= 1; //??0,1???!
Mod mo(n);
for (int i = 0; i < S; ++i)
{
if (!(n % p[i]))
return n == p[i];
for (t = mo.pow(p[i], u = d); t != n - 1 && t != 1 && u != n - 1;)
t = mo.mul(t, t), u <<= 1;
if (t != n - 1 && !(u & 1))
return 0;
}
return 1;
}
void fac(ll n, vector<ll> &factor)
{
/*
if (n < e.m.size()) //????????,??????????????
{
for (; n > 1; n /= e.m[n])
factor.push_back(e.m[n]);
return;
}
*/
if (isPrime(n))
return factor.push_back(n);
Mod mo(n);
for (ll c = 1;; ++c)
for (ll i = 0, k = 1, x = rand() % (n - 1) + 1, y, p;;)
{
if (++i == k)
y = x, k <<= 1;
if (x = mo.add(mo.mul(x, x), c), p = __gcd(abs(x - y), n), p == n)
break;
if (p > 1)
return fac(p, factor), fac(n / p, factor);
}
}
} pr;
ll n;
vector<ll> v;
int main(void)
{
scanf("%lld", &n);
n = n * (n + 1) / 2;
pr.fac(n, v);
ll m = 1e18;
for (int i = 0; i < v.size(); i++)
m = min(m, v[i]);
printf("%lld\n", n / m);
}
Function
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct hs
{
int x, a, b;
bool operator<(const hs &h) const
{
return (2 * x + 1) * a + b > (2 * h.x + 1) * h.a + h.b;
}
};
priority_queue<hs> pq;
int main(void)
{
int n, m;
scanf("%d%d", &n, &m);
ll ans = 0;
while (n--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
ans += a + b + c;
m--;
pq.push({1, a, b});
}
while (m--)
{
hs tem = pq.top();
//cout<<tem.x<<" "<<tem.a<<" "<<tem.b<<endl;
pq.pop();
ans += (2 * tem.x + 1) * tem.a + tem.b;
tem.x++;
pq.push(tem);
}
printf("%lld\n", ans);
}
Tree
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 9, NPOS = -1;
struct SegmentTree
{
struct Seg
{
int l, r;
ll flag, sum;
void upd()
{
sum = sqrt(sum);
if (sum <= 1)
flag = 1;
}
friend Seg operator+(const Seg &lc, const Seg &rc) { return {lc.l, rc.r, lc.flag && rc.flag, lc.sum + rc.sum}; }
};
struct Node : Seg
{
int lc, rc;
};
vector<Node> v;
SegmentTree(int l, int r, const vector<ll> &a) { build(l, r, a); }
void build(int l, int r, const vector<ll> &a)
{
int rt = v.size();
v.push_back({});
v[rt].Seg::operator=({l, r, a[l] <= 1, a[l]});
v[rt].lc = v[rt].rc = NPOS;
if (l < r)
{
int m = v[rt].l + (v[rt].r - v[rt].l >> 1);
if (v[rt].lc == NPOS)
v[rt].lc = v.size(), build(v[rt].l, m, a);
if (v[rt].rc == NPOS)
v[rt].rc = v.size(), build(m + 1, v[rt].r, a);
v[rt].Seg::operator=(v[v[rt].lc] + v[v[rt].rc]);
}
}
void upd(int l, int r, int rt = 0)
{
if (v[rt].flag)
return;
if (v[rt].l >= v[rt].r)
{
v[rt].upd();
return;
}
if (r <= v[v[rt].lc].r)
upd(l, r, v[rt].lc);
else if (l >= v[v[rt].rc].l)
upd(l, r, v[rt].rc);
else
upd(l, v[v[rt].lc].r, v[rt].lc), upd(v[v[rt].rc].l, r, v[rt].rc);
v[rt].Seg::operator=(v[v[rt].lc] + v[v[rt].rc]);
}
Seg ask(int l, int r, int rt = 0)
{
if (l <= v[rt].l && v[rt].r <= r)
return v[rt];
if (r <= v[v[rt].lc].r)
return ask(l, r, v[rt].lc);
if (l >= v[v[rt].rc].l)
return ask(l, r, v[rt].rc);
return ask(l, v[v[rt].lc].r, v[rt].lc) + ask(v[v[rt].rc].l, r, v[rt].rc);
}
};
struct Graph
{
struct Vertex
{
vector<int> o, i; //相关出边和入边编å·
int siz, dep, top, dfn; //æ ‘é「¾å‰–分ä¸ä½¿ç」¨ï¼Œä¾æ¬¡ä»£è¡¨åæ ‘èŠ‚ç‚¹æ•°ã€æ·±åº¦ã€æ‰€åœ¨é「¾çš„顶端节点ã€dfsåº
};
typedef pair<int, int> Edge;
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
int ch(int u, int i = 0) { return e[v[u].o[i]].second; } //u的第i个å©å节点
int fa(int u, int i = 0) { return e[v[u].i[i]].first; } //u的第i个父节点
};
ll a[N];
struct Diagram : Graph
{
SegmentTree data;
Diagram(const Graph &g, int root) : Graph(g.v.size()), data(0, 0, {0})
{
build(root, g);
int cnt = v[root].dfn = v[root].dep = 1;
dfs(v[root].top = root, cnt);
vector<ll> b(cnt + 1);
for (int i = 0; i < v.size(); ++i)
b[v[i].dfn] = a[i];
data = SegmentTree(1, cnt, b);
}
void build(int u, const Graph &g) //æ— å‘图dfså»ºæ ‘ï¼Œä¸」é‡è¾¹åœ¨æœ€å‰ï¼Œuä¸ºæ ¹èŠ‚ç‚¹
{
v[u].siz = 1;
for (int i = 0, k, to; i < g.v[u].o.size(); ++i)
if (k = g.v[u].o[i], to = g.e[k].second, !v[to].siz) //没访问过的点siz默认0
{
build(to, g);
v[u].siz += v[to].siz;
Graph::add(g.e[k]);
if (v[ch(u)].siz < v[to].siz) //é‡è¾¹ç§»åˆ°æœ€å‰
swap(v[u].o.front(), v[u].o.back());
}
}
void dfs(int u, int &cnt)
{
for (int i = 0, to; i < v[u].o.size(); ++i)
{
v[to = ch(u, i)].dfn = ++cnt;
v[to].top = i ? to : v[u].top;
v[to].dep = v[u].dep + 1;
dfs(to, cnt);
}
}
ll ask(int x, int y)
{
ll ans = 0;
for (; v[x].top != v[y].top; x = fa(v[x].top))
{
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
ans += data.ask(v[v[x].top].dfn, v[x].dfn).sum;
}
if (v[x].dep < v[y].dep)
swap(x, y);
return ans += data.ask(v[y].dfn, v[x].dfn).sum;
}
void upd(int x, int y)
{
for (; v[x].top != v[y].top; x = fa(v[x].top))
{
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
data.upd(v[v[x].top].dfn, v[x].dfn);
}
if (v[x].dep < v[y].dep)
swap(x, y);
data.upd(v[y].dfn, v[x].dfn);
}
};
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for (int i = 0; i < n; ++i)
scanf("%lld", &a[i]);
Graph g(n);
for (int i = 1, u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
g.add({u - 1, v - 1});
g.add({v - 1, u - 1});
}
Diagram t(g, 0);
for (int i = 0, o, u, v; i < q; ++i)
{
scanf("%d%d%d", &o, &u, &v);
if (o)
printf("%lld\n", t.ask(u - 1, v - 1));
else
t.upd(u - 1, v - 1);
}
}
Checkout
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 9;
struct Vefaex
{
vector<int> g;
int a, fa;
unordered_map<int, ll> mp;
} v[N];
int n, m;
ll sum = 0, ans[N];
void dfs1(int u)
{
for (auto to : v[u].g)
if (to != v[u].fa)
{
v[to].fa = u;
sum += v[u].mp[v[to].a]++ + (v[to].a == v[u].a);
dfs1(to);
}
}
void dfs2(int u)
{
for (auto to : v[u].g)
if (to != v[u].fa)
dfs2(to);
int fa = v[u].fa;
if (fa)
{
ll res = sum - v[fa].mp[v[fa].a];
--v[fa].mp[v[u].a];
for (auto tp : v[u].mp)
res += tp.second * v[fa].mp[tp.first];
++v[fa].mp[v[u].a];
ans[fa] = max(ans[fa], res);
}
if (v[u].g.size() < 2 && v[u].fa)
{
ans[u] = sum - v[fa].mp[v[u].a] + 1;
if (v[fa].a == v[u].a)
--ans[u];
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &v[i].a);
for (int i = 1, x, y; i < n; ++i)
{
scanf("%d%d", &x, &y);
v[x].g.push_back(y);
v[y].g.push_back(x);
}
dfs1(1);
dfs2(1);
for (int i = 1; i <= n; ++i)
printf("%lld%c", ans[i], i < n ? ' ' : '\n');
}
String
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, L, t;
int f[maxn][11][27], Min1[maxn][11], Min2[maxn][11], M1[maxn][11], M2[maxn][11];
char ch[maxn];
int main()
{
scanf("%d%d%d", &n, &L, &t);
scanf("%s", ch);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= t; j++)
for (int k = 0; k <= 26; k++)
f[i][j][k] = n;
memset(M1, -1, sizeof(M1));
memset(M2, -1, sizeof(M2));
int par = 1;
f[0][par][ch[0] - 'a'] = 0;
for (int i = 1; i < n; i++)
{
if (ch[i] != ch[i - 1])
par++;
if (par > t)
break;
f[i][par][ch[i] - 'a'] = 0;
}
for (int i = 0; i < n; i++)
for (int k = 1; k <= t; k++)
{
for (int a = 0; a < 26; a++)
{
if (i > 0 && a == ch[i] - 'a')
f[i][k][a] = min(f[i][k][a], f[i - 1][k][a]);
if (i - L < 0)
f[i][k][a] = min(f[i][k][a], 1);
else
{
if (a != M1[i - L][k - 1] && M1[i - L][k - 1] != -1)
f[i][k][a] = min(f[i][k][a], Min1[i - L][k - 1] + 1);
if (a != M2[i - L][k - 1] && M2[i - L][k - 1] != -1)
f[i][k][a] = min(f[i][k][a], Min2[i - L][k - 1] + 1);
if (a == M1[i - L][k] && M1[i - L][k] != -1)
f[i][k][a] = min(f[i][k][a], Min1[i - L][k] + 1);
if (a == M2[i - L][k] && M2[i - L][k] != -1)
f[i][k][a] = min(f[i][k][a], Min2[i - L][k] + 1);
}
}
Min1[i][k] = n + 1;
Min2[i][k] = n + 1;
for (int a = 0; a < 26; a++)
{
if (Min1[i][k] > f[i][k][a])
{
Min1[i][k] = f[i][k][a];
M1[i][k] = a;
}
else if (Min2[i][k] > f[i][k][a])
{
Min2[i][k] = f[i][k][a];
M2[i][k] = a;
}
}
}
int ans = n;
for (int k = 1; k <= t; k++)
for (int a = 0; a < 26; a++)
ans = min(ans, f[n - 1][k][a]);
printf("%d\n", ans);
}
Circle
#include <bits/stdc++.h>
#define ld double
using namespace std;
ld a, x, ans;
int n;
const ld pi = acos(-1.0);
int main(void)
{
while (cin >> n)
{
a = 2 * pi / n;
ans = n * sin(a) / 2;
x = sin(a / 4);
ans += x * x * 2 * sin(a / 2);
printf("%.6lf\n", ans);
}
}
Clock
#include <bits/stdc++.h>
#define maxn 2000004
using namespace std;
int n, a, b, c, now;
int d[maxn];
int main(void)
{
scanf("%d", &n);
scanf("%d%d%d", &a, &b, &c);
a %= 12;
now = a * 3600 + 60 * b + c;
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d", &a, &b, &c);
a %= 12;
int val = a * 3600 + b * 60 + c;
d[i] = val;
}
d[0] = now;
sort(d, d + n + 1);
n = unique(d, d + 1 + n) - d - 1;
int loc = lower_bound(d, d + n + 1, now) - d;
//cout<<n<<" "<<loc<<endl;
for (int i = n + 1; i <= 2 * n + 1; i++)
d[i] = d[i - n - 1] + 43200;
//for(int i=0;i<=2*n+1;i++)cout<<i<<" "<<d[i]<<endl;
int dns = 0x3f3f3f3f;
for (int i = 0; i <= n; i++)
{
if (i == 0)
{
dns = min(dns, min(d[loc] - d[0], d[n] - d[loc]) + d[n] - d[0]);
}
else if (i <= loc)
{
//cout<<d[i-1]<<endl;
dns = min(dns, min(d[loc] - d[i], d[i - 1 + n + 1] - d[loc]) + 43200 - d[i] + d[i - 1]);
}
else if (i > loc)
{
dns = min(dns, min(d[i - 1] - d[loc], d[loc + n + 1] - d[i]) + 43200 - d[i] + d[i - 1]);
}
}
printf("%.2lf\n", dns * 6.0);
}
Union
#include <bits/stdc++.h>
#define mod 1000000007
#define inv6 166666668
#define inv2 500000004
#define ll long long
ll c[100], jc[100], jcn[100];
ll ksm(ll a, ll b)
{
ll ret = 1, tem = a;
while (b)
{
if (b & 1)
ret = ret * tem % mod;
tem = tem * tem % mod;
b >>= 1;
}
return ret;
}
using namespace std;
int main(void)
{
int k, a1, a2, a3, a4, a5, a6, a7, n;
scanf("%d%d%d%d%d%d%d%d%d", &n, &k, &a1, &a2, &a3, &a4, &a5, &a6, &a7);
jc[0] = jcn[0] = c[0] = 1;
for (int i = 1; i <= k; i++)
{
jc[i] = jc[i - 1] * i % mod;
jcn[i] = ksm(jc[i], mod - 2);
c[i] = c[i - 1] * (n - i + 1) % mod;
}
ll ans = 0;
for (int s = a7; s <= k; s++)
{
for (int b1 = 0; b1 <= s - a5; b1++)
{
for (int b2 = 0; b2 * 2 + b1 <= k; b2++)
{
for (int b3 = 0; b3 * 3 + b2 * 2 + b1 <= k; b3++)
{
for (int b4 = max(a1 - b1 - b2 - b3, 0); b4 * 2 + b3 * 3 + b2 * 2 + b1 <= k; b4++)
{
for (int b5 = 0; b5 <= s - a6 && b5 + b4 * 2 + b3 * 3 + b2 * 2 + b1 <= k; b5++)
{
for (int b6 = max(a2 - b2 - b3 - b5, 0); b6 * 2 + b5 + b4 * 2 + b3 * 3 + b2 * 2 + b1 <= k; b6++)
{
//for(int b7=max(a3-b3-b4-b6-b7,0);b7+b6*2+b5+b4*2+b3*3+b2*2+b1<=k&&b7<=s-a4;b7++){
int b7 = s - b1 - b2 - b3 - b4 - b5 - b6;
int s1 = b1 + b2 + b3 + b4, s2 = b2 + b3 + b5 + b6, s3 = b3 + b4 + b6 + b7;
if (b7 <= s - a4 && k - (b6 * 2 + b5 + b4 * 2 + b3 * 3 + b2 * 2 + b1) == b7 && b7 >= a3 - b3 - b4 - b6 - b7)
{
//if(b3==s)ans=(ans+(ll)c[s]*inv6%mod)%mod;
//else if(b2+b3==s1&&b2+b3==s2)ans=(ans+(ll)c[s]*inv2%mod)%mod;
//else if(b6+b3==s2&&b6+b3==s3)ans=(ans+(ll)c[s]*inv2%mod)%mod;
//else if(b4+b3==s1&&b4+b3==s3)ans=(ans+(ll)c[s]*inv2%mod)%mod;
ans = (ans + c[s] * jcn[b1] % mod * jcn[b2] % mod * jcn[b3] % mod * jcn[b4] % mod * jcn[b5] % mod * jcn[b6] % mod * jcn[b7] % mod) % mod;
//puts("");
//cout<<b1<<" "<<b2<<" "<<b3<<" "<<b4<<" "<<b5<<" "<<b6<<" "<<b7<<endl;
//cout<<b1+b2+b3+b4<<" "<<b2+b3+b5+b6<<" "<<b3+b4+b6+b7<<" "<<s-b7<<" "<<s-b5<<" "<<s-b1<<" "<<s<<endl;;
}
}
}
}
}
}
}
}
printf("%lld\n", ans);
}
Tangram
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
int main()
{
while (scanf("%lld", &n) != EOF)
{
if (n == 0)
printf("7\n");
else
printf("%lld\n", 7ll + (6ll + (6ll + (n - 1ll))) * n / 2ll);
}
}
Tetris
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int a[4][4] = {1, 1, 1, 3, 2, 1, 3, 3, 2, 2, 4, 3, 2, 4, 4, 4};
int n, m;
int main()
{
while (~scanf("%d%d", &n, &m))
{
if (n % 4 != 0 || m % 4 != 0)
printf(" no response\n");
else
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
printf("%d", a[i % 4][j % 4]);
printf("\n");
}
}
}