T1
超短代码
#include <bits/stdc++.h>
std::map<char, int> fl;
std::string a;
int n;
int main() {
std::cin >> n >> a;
for (int i = 0; i < a.size(); i++) fl[a[i]]++;
for (int i = 0; i < a.size(); i++)
if (!(fl[a[i]] - 1))
return !(std::cout << a[i]);
return !(std::cout << -1);
}
T2
暴力模拟
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define Sig signed
#define ll long long
#define Il inline
#define fup(i, a, b) for (int(i) = (a); (i) <= (b); ++(i))
#define fdown(i, a, b) for (int(i) = (a); (i) >= (b); --(i))
int a, b;
using namespace std;
Il int R() {
int p = 0, q = 1;
char ch = getchar();
while (!isdigit(ch)) q = (ch == '-') ? -1 : 1, ch = getchar();
while (isdigit(ch)) p = (p << 3) + (p << 1) + (ch ^ 48), ch = getchar();
return p * q;
}
int ans, flag;
Sig main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> a >> b;
flag = a;
fup(i, a, b) {
int x = i, s = 0;
while (x) {
if (x % 10 == 0 || x % 10 == 6 || x % 10 == 9)
s++;
if (x % 10 == 8)
s += 2;
x /= 10;
}
if (s > ans)
ans = s, flag = i;
}
cout << flag;
return 0;
}
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Sig signed
#define ll long long
#define Il inline
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);++(i))
#define fdown(i,a,b) for(int (i)=(a);(i)>=(b);--(i))
using namespace std;
Il int R()
{
int p=0,q=1;
char ch=getchar();
while(!isdigit(ch)) q=(ch=='-')?-1:1,ch=getchar();
while(isdigit(ch)) p=(p<<3)+(p<<1)+(ch^48),ch=getchar();
return p*q;
}
const int N=2500,M=2*N,L=1e5+10;
ll n,b[L],g[L],ansb[L],ansg[L],ans,k;
Sig main(void)
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
n=R();
fup(i,1,n) b[i]=R(),ansb[b[i]+M]++;
fup(i,1,n) g[i]=R(),ansg[g[i]+M]++;
for(int i=N+M;i>=N;i--)
{
for(int j=N+M;j>=N;j--)
{
if(((i-M)>0&&(j-M)<0)||((i-M)<0&&(j-M)>0))
{
if(!ansb[i]) break;
if(i+j<2*M)
{
ans+=min(ansb[i],ansg[j]);
k=min(ansb[i],ansg[j]);
ansb[i]-=k;
ansg[j]-=k;
}
}
}
}
cout<<ans;
return 0;
}
贪心吧
男找高配女找低
男找低配女找高
T4
#include <bits/stdc++.h>
using namespace std;
int n, len, ax[1000], top, fs, id;
string s, ay[1000];
char a;
signed main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
while (n--) {
cin >> s;
len = s.size();
for (int i = 0; i < len; i++) {
top++;
if (s[i] == ':' && s[i + 1] == ':') {
i += 2;
fs = top;
top++;
} else if (top != 1)
i++;
while (s[i] != ':' && i < len) {
ay[top] += s[i];
ax[top]++;
i++;
}
i--;
}
id = 9 - top;
for (int i = 1; i <= top; i++) {
if (i == fs)
for (int j = 1; j <= id; j++) {
if (i + j - 1 != 8)
cout << "0000:";
else
cout << "0000";
}
else {
for (int j = 1; j <= 4 - ax[i]; j++) cout << "0";
if (i != top)
cout << ay[i] << ":";
else
cout << ay[i];
}
}
cout << '\n';
top = fs = id = 0;
for (int i = 1; i <= 100; i++) {
ax[i] = 0;
ay[i] = "";
}
}
return 0;
}
模拟即可
T5
因为很多爆炸都是同时进行的，所以比较水
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll r, c;
ll e[2505], f[2505];
ll ans;
char mp[55][55];
struct Ways {
ll u, v, w;
} way[1662505];
ll tot;
int cmp(Ways A, Ways B) { return A.w < B.w; }
signed main(void) {
ios::sync_with_stdio(false);
cin >> r >> c;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) cin >> mp[i][j];
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
if (mp[i][j] == 'X')
for (int k = 1; k <= r; k++)
for (int l = 1; l <= c; l++)
if (mp[k][l] == 'L')
way[++tot].u = (i - 1) * c + j, way[tot].v = (k - 1) * c + l,
way[tot].w = (i - k) * (i - k) + (j - l) * (j - l);
sort(way + 1, way + 1 + tot, cmp);
for (int i = 1; i <= tot; i++) {
if (!e[way[i].u]) {
if (!f[way[i].v])
f[way[i].v] = way[i].w, e[way[i].u] = 1;
else if (f[way[i].v] == way[i].w)
++ans, e[way[i].u] = 1, f[way[i].v] = -1;
}
}
cout << ans;
return 0;
}
T6
什么玩意儿的奇环数
本来写网络流的写T了,心态炸裂
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define Sig signed
#define ll long long
#define Il inline
#define fup(i, a, b) for (int(i) = (a); (i) <= (b); ++(i))
#define fdown(i, a, b) for (int(i) = (a); (i) >= (b); --(i))
using namespace std;
const int N = 2e5 + 10, inf = 0x3f3f3f3f;
Il int R() {
int p = 0, q = 1;
char ch = getchar();
while (!isdigit(ch)) q = (ch == '-') ? -1 : 1, ch = getchar();
while (isdigit(ch)) p = (p << 3) + (p << 1) + (ch ^ 48), ch = getchar();
return p * q;
}
int n, ans;
int stk[N], tot;
int nxt[N], cost[N], val[N], mark[N];
void work(int x) {
int ys = inf, mrfz;
for (int l = nxt[x]; mark[l]; x = l, l = nxt[l]) {
mark[l] = 0;
mrfz = max(val[l] - cost[x], 0);
ans += mrfz;
ys = min(ys, val[l] - mrfz);
}
ans += ys;
}
Sig main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
n = R();
fup(i, 1, n) nxt[i] = R(), cost[i] = R(), val[i] = cost[i], ++mark[nxt[i]];
fup(i, 1, n) if (!mark[i]) stk[++tot] = i;
while (tot) {
int y = stk[tot--];
ans += val[y];
val[nxt[y]] = max(val[nxt[y]] - cost[y], 0);
if (!(--mark[nxt[y]]))
stk[++tot] = nxt[y];
}
fup(i, 1, n) if (mark[i]) work(i);
printf("%d", ans);
return 0;
}
T7
重生吧，我的欧拉
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define Sig signed
#define ll long long
#define Il inline
#define pii pair<int, int>
#define mpr make_pair
#define ft first
#define sd second
#define fup(i, a, b) for (int(i) = (a); (i) <= (b); ++(i))
#define fdown(i, a, b) for (int(i) = (a); (i) >= (b); --(i))
using namespace std;
const int N = 1e6 + 10;
Il int read() {
int p = 0, q = 1;
char ch = getchar();
while (!isdigit(ch)) q = (ch == '-') ? -1 : 1, ch = getchar();
while (isdigit(ch)) p = (p << 3) + (p << 1) + (ch ^ 48), ch = getchar();
return p * q;
}
struct Node {
int to, nxt;
} node[N << 2];
pii ans[N << 2];
int n, m, tmp = -1, cnt = 1, tot;
int ind[N], hd[N], sk[N], vis[N], S[N], mks[N];
void ins(int u, int v) {
node[++cnt].nxt = hd[u];
hd[u] = cnt;
node[cnt].to = v;
}
void dfs(int x) {
vis[x] = 1;
if (ind[x] & 1)
sk[++sk[0]] = x;
for (int i = hd[x]; i; i = node[i].nxt)
if (!vis[node[i].to])
dfs(node[i].to);
}
void work(int x) {
S[0] = 1, S[1] = x;
while (S[0]) {
Nxtcirc:
x = S[S[0]];
for (int &i = hd[x]; i; i = node[i].nxt) {
if (!mks[i]) {
mks[i] = mks[i ^ 1] = 1;
S[++S[0]] = node[i].to;
goto Nxtcirc;
}
}
sk[++sk[0]] = x;
--S[0];
}
}
Sig main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
n = read(), m = read();
int x, y;
fup(i, 1, m) x = read(), y = read(), ins(x, y), ins(y, x), ++ind[x], ++ind[y];
fup(i, 1, n) {
if (ind[i] && !vis[i]) {
sk[0] = 0, dfs(i), hd[0] = 0;
if (!sk[0])
ins(i, 0), ins(i, 0), ins(0, i), ins(0, i);
else
while (sk[0]) ins(sk[sk[0]], 0), ins(0, sk[sk[0]--]);
work(0);
while (sk[0] > 1) {
if (sk[sk[0]])
ans[++tot] = mpr(0, sk[sk[0]--]);
else
--sk[0], ans[++tot] = mpr(1, sk[sk[0]--]), ++tmp;
}
}
}
printf("%d\n%d\n", tmp, ans[1].sd);
fup(i, 2, tot) printf("%d %d\n", ans[i].ft, ans[i].sd);
return 0;
}
T8
WA 了，请教各位 DALAO
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define Sig signed
#define ll long long
#define Il inline
#define pii pair<int, int>
#define Vt vector
#define Stk stack
#define mpr make_pair
#define ft first
#define sd second
#define pb push_back
#define fup(i, a, b) for (int(i) = (a); (i) <= (b); ++(i))
#define fdown(i, a, b) for (int(i) = (a); (i) >= (b); --(i))
using namespace std;
const int N = 5e5 + 10;
int n, len, tot, aln, times, sct;
int ch[N << 1][2], rd[N << 1], tn[N << 1];
int dfn[N << 3], low[N << 3], decideb[N << 3];
char cod[N];
Vt<int> ts[N << 3]; // 2-SAT
Stk<int> stk;
Il int read() {
int p = 0, q = 1;
char ch = getchar();
while (!isdigit(ch)) q = (ch == '-') ? -1 : 1, ch = getchar();
while (isdigit(ch)) p = (p << 3) + (p << 1) + (ch ^ 48), ch = getchar();
return p * q;
}
void ins(char s[], int id) {
int y = 0;
for (int i = 0; s[i]; ++i) {
int ach = s[i] - '0';
if (s[i] == '?')
ach = (id & 1);
if (!ch[y][ach])
ch[y][ach] = ++tot;
y = ch[y][ach];
}
if (not rd[y]) {
rd[y] = tn[y] = ++aln;
ts[id].pb(rd[y]);
ts[tn[y]].pb(id ^ 1);
} else {
ts[id].pb(tn[y]);
ts[rd[y]].pb(id ^ 1);
ts[id].pb(++aln);
ts[rd[y]].pb(aln);
rd[y] = aln;
ts[++aln].pb(id ^ 1);
ts[aln].pb(tn[y]);
tn[y] = aln;
}
}
void dfs(int x, int xp, int yp) {
if (rd[x]) {
if (!xp)
xp = rd[x], yp = tn[x];
else {
ts[rd[x]].pb(yp);
ts[xp].pb(tn[x]);
ts[xp].pb(++aln);
ts[rd[x]].pb(aln);
xp = aln;
ts[++aln].pb(yp);
ts[aln].pb(tn[x]);
yp = aln;
}
}
if (ch[x][0])
dfs(ch[x][0], xp, yp);
if (ch[x][1])
dfs(ch[x][1], xp, yp);
}
void tarjan(int x) {
dfn[x] = low[x] = ++times;
stk.push(x);
for (auto y : ts[x]) {
if (!dfn[y])
tarjan(y), low[x] = min(low[x], low[y]);
else if (!decideb[y])
low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x]) {
++sct;
int y;
do {
y = stk.top();
stk.pop();
decideb[y] = sct;
} while (x != y);
}
}
Sig main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
n = read(), aln = (n + 1) * 2;
fup(i, 1, n) {
int vts = i * 2;
scanf("%s", cod);
ins(cod, vts);
len = strlen(cod);
if (count(cod, cod + len, '?'))
ins(cod, vts + 1);
else
ts[vts + 1].pb(vts);
}
dfs(0, 0, 0);
fup(i, 1, n) {
int vts = i * 2;
if (!dfn[vts])
tarjan(vts);
if (!dfn[vts + 1])
tarjan(vts + 1);
if (decideb[vts] == decideb[vts + 1]) {
return !(puts("NO"));
}
}
return !(puts("YES"));
}
补完blog
交电脑去了