# D1 T1 小凯的疑惑

——答案是 $a \times b – a – b$

#include <bits/stdc++.h>

using namespace std;

int a, b;

int main()
{
scanf("%d%d", &a, &b);
printf("%lld\n", 1ll * a * b - a - b);
return 0;
}


# D1 T2 时间复杂度

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c;bool flag=0;dig=0;
while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
if(flag)dig=-dig;
}
template<typename _Tp>inline void SPIN(_Tp&dig)
{
char c;dig=0;
while(c=getchar(),(!isdigit(c))&&c!='n');
if(c=='n'){dig=-1;return;}
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct F{char v;int a,b;};
int T,L,w,ans;
bool hash[30];
char buff[1000];
stack<F> st;
{
scanf("%s",buff);
if(buff[2]=='1'){w=0;return;}
int tmp=0;
w=0;
while(!isdigit(buff[tmp]))tmp++;
while(isdigit(buff[tmp]))w=w*10+buff[tmp]-'0',tmp++;
}
void getl()
{
char c;
while(c=getchar(),c!='\n'&&c!='\r'&&c!=EOF);
}
int main()
{
IN(T);
while(T--)
{
while(!st.empty())st.pop();
for(int line=1,tmp=0,v0=0;line<=L;line++)
{
scanf("%s",buff);
if(buff[0]=='F')
{
scanf("%s",buff);
if(hash[buff[0]-'a'])
{
puts("ERR");
for(int i=line;i<=L;i++)getl();
goto end;
}
hash[buff[0]-'a']=1;
F p=(F){buff[0],0,0};
SPIN(p.a),SPIN(p.b),st.push(p);
if(p.a>=0&&p.b<0)tmp++;
else if(p.a<0&&p.b>=0)v0++;
else if(p.a>p.b)v0++;
}
else
{
if(st.empty())
{
puts("ERR");
for(int i=line;i<=L;i++)getl();
goto end;
}
F p=st.top();st.pop();
hash[p.v-'a']=0;
if(!v0)ans=max(ans,tmp);
if(p.a>=0&&p.b<0)tmp--;
else if(p.a<0&&p.b>=0)v0--;
else if(p.a>p.b)v0--;
}
}
if(st.size())puts("ERR");
else
{
if(ans==w)puts("Yes");
else puts("No");
}
end:continue;
}
return 0;
}


# D1T3 逛公园

#include <bits/stdc++.h>

#define NS (100005)
#define MS (200005)
#define KS (55)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct Graph
{
int head[NS], nxt[MS], to[MS], w[MS], sz;
void init() {memset(head, -1, sizeof(head)), sz = 0;}
Graph() {init();}
void push(int a, int b, int c)
{
nxt[sz] = head[a], to[sz] = b, w[sz] = c, head[a] = sz++;
}
int operator [] (const int a) const {return to[a];}
} g, G;

int T, n, m, k, p, dis[NS];

bool vis[NS];

priority_queue<PII, vector<PII>, greater<PII> > pq;

void Dij()
{
memset(vis, 0, sizeof(vis)), memset(dis, 127, sizeof(dis));
dis[n] = 0, pq.push(PII(0, n));
while (!pq.empty())
{
int F = pq.top().SEC; pq.pop();
if (vis[F]) continue;
vis[F] = 1;
for (int i = g.head[F]; ~i; i = g.nxt[i])
if (dis[g[i]] > dis[F] + g.w[i])
dis[g[i]] = dis[F] + g.w[i], pq.push(PII(dis[g[i]], g[i]));
}
}

int f[NS][KS];

bool book[NS][KS];

int Dfs(int a, int x)
{
if (book[a][x]) return -1;
int& F = f[a][x];
if (F != -1) return F;
book[a][x] = 1;
if (a == n) F = 1; else F = 0;
for (int i = G.head[a], j; ~i; i = G.nxt[i])
{
j = dis[G[i]] + G.w[i] - dis[a];
if (j <= x)
{
j = Dfs(G[i], x - j);
if (j == -1) return -1;
F = (F + j) % p;
}
}
book[a][x] = 0; return F;
}

int main(int argc, char const* argv[])
{
IN(T);
while (T--)
{
IN(n), IN(m), IN(k), IN(p), g.init(), G.init();
for (int i = 1, a, b, c; i <= m; i += 1)
IN(a), IN(b), IN(c), G.push(a, b, c), g.push(b, a, c);
Dij(), memset(f, -1, sizeof(f)), memset(book, 0, sizeof(book));
printf("%d\n", Dfs(1, k));
}
return 0;
}


# D2T1 奶酪

#include<bits/stdc++.h>
using namespace std;
int t,n,h,r,u;
int x[1005],y[1005],z[1005];
int ansz,maxz=-0x7fffffff;
int minz=0x7ffffff;
int ans[25],visited[1005];
double dis[1005][1005];
double diss(int a,int b)
{
double p;
p=sqrt(pow(abs(double(x[a])-double(x[b])),2)+pow(abs(double(y[a])-double(y[b])),2)+pow(abs(double(z[a])-double(z[b])),2));
return p;
}
int search(int g)
{
for(int i=1;i<=n;i++)
{
if((i!=g)&&(dis[i][g]<=(2*double(r)))&&(!visited[i]))
{
if(z[i]>ansz){ansz=z[i];visited[i]=1;}
if((z[i]+r)>=h){u=1;break;}
}
}
return 0;
}
int main()
{
scanf("%d",&t);
for(int k=1;k<=t;k++)
{
scanf("%d%d%d",&n,&h,&r);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x[i],&y[i],&z[i]);
if(z[i]>maxz)maxz=z[i];
if(z[i]<minz)minz=z[i];
for(int j=1;j<=i-1;j++)
dis[i][j]=dis[j][i]=diss(i,j);
}
if(((maxz+r)<h)||((minz-r)>0)){ans[k]=0;continue;}
for(int i=1;i<=n;i++)
{
if(((z[i]-r)<=0)&&!u)
{
ansz=z[i];
if((ansz+r)>=h){u=1;break;}
visited[i]=1;
search(i);
memset(visited,0,sizeof(visited));
}
if(u)break;
}
if(u)ans[k]=1;
else ans[k]=0;
u=0;
}
for(int i=1;i<=t;i++)
{
if(ans[i])printf("Yes\n");
else printf("No\n");
}
return 0;
}


# D2T2 宝藏

#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>

#define NS (12)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

typedef long long LL;

int n, m, d[NS][NS], dis[NS];

int v[1 << NS][1 << NS], f[NS][1 << NS], ans = INT_MAX;

int main(int argc, char const* argv[])
{
IN(n), IN(m), memset(d, 63, sizeof(d)), memset(v, 63, sizeof(v));
if (n == 1) puts("0"), exit(0);
for (int i = 1, a, b, c; i <= m; i += 1)
{
IN(a), IN(b), IN(c), a--, b--;
d[a][b] = d[b][a] = min(d[a][b], c);
}
for (int i = (1 << n) - 1; i > 1; i -= 1)
for (int j = ((i - 1) & i); j; j = ((j - 1) & i))
{
memset(dis, 63, sizeof(dis)), v[j][i] = 0;
for (int x = 0; x < n; x += 1) if ((j >> x) & 1)
for (int y = 0; y < n; y += 1)
if (((i >> y) & 1) && !((j >> y) & 1))
dis[y] = min(dis[y], d[x][y]);
for (int y = 0; y < n; y += 1)
if (((i >> y) & 1) && !((j >> y) & 1))
{
if (dis[y] > 1e9) {v[j][i] = 1e9; break;}
else v[j][i] += dis[y];
}
}
for (int x = 0; x < n; x += 1)
{
memset(f, 63, sizeof(f)), f[0][1 << x] = 0;
for (int i = 1; i < n; i += 1)
{
for (int s = (1 << n) - 1; s > 1; s -= 1)
for (int z = ((s - 1) & s); z; z = ((z - 1) & s))
f[i][s] = min((LL)f[i][s], (LL)f[i - 1][z] + (LL)i * v[z][s]);
ans = min(ans, f[i][(1 << n) - 1]);
}
}
printf("%d\n", ans);
return 0;
}


# D2T3 列队

#include <bits/stdc++.h>

#define NS (300005)

typedef long long LL;

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, m, q, M, root[NS], del[NS * 20], s[NS * 20][2], sz;

vector<LL> g[NS];

int Query(int x, int l, int r, int a)
{
if (l == r) return l;
int mid = (l + r) >> 1, tmp = mid - l + 1 - del[s[a][0]];
if (tmp >= x)
return Query(x, l, mid, s[a][0]);
return Query(x - tmp, mid + 1, r, s[a][1]);
}

void Del(int x, int l, int r, int& a)
{
if (!a) a = ++sz;
del[a]++;
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) Del(x, l, mid, s[a][0]);
else Del(x, mid + 1, r, s[a][1]);
}

LL Rm(int x, LL v)
{
int pos = Query(x, 1, M, root[n + 1]); LL res = 0;
Del(pos, 1, M, root[n + 1]);
if (pos <= n) res = 1ll * pos * m;
else res = g[n + 1][pos - n - 1];
if (v) g[n + 1].push_back(v);
else g[n + 1].push_back(res);
return res;
}

void Work(int x, int y)
{
int pos = Query(y, 1, M, root[x]);
Del(pos, 1, M, root[x]);
LL tmp = 0;
if (pos < m) tmp = 1ll * (x - 1) * m + pos;
else tmp = g[x][pos - m];
g[x].push_back(Rm(x, tmp)), printf("%lld\n", tmp);
}

int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(q), M = max(n, m) + q;
int x, y;
while (q--)
{
IN(x), IN(y);
if (y < m) Work(x, y);
else printf("%lld\n", Rm(x, 0));
}
return 0;
}