感觉现在Edu场比以前的难多了……
A：
温暖人心
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int maxn = 3e5 + ;
int n;
char s[maxn]; int main()
{
scanf("%d", &n);
scanf("%s", s + );
rep0(i, , n)
{
if (s[i] > s[i + ])
return cout << "YES" << endl << i << " " << i + , ;
}
puts("NO");
return ;
}
B：
数前n-10个数里几个8几个非8就完事了，正确性显然
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int maxn = 1e5 + ;
char s[maxn];
int n, numOfEight = , re = ; int main()
{
scanf("%d", &n);
scanf("%s", s + );
rep1(i, , n - )
if (s[i] == '') numOfEight++; else re++;
if (numOfEight > re) puts("YES"); else puts("NO");
return ;
}
C：
计算所有时间区间gcd，找是否存在p能整除gcd，正确性显然
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int maxn = 3e5 + ;
int n, m;
ll s, currX, lastX, currP, ansPos = , gcd; int main()
{
scanf("%d%d", &n, &m);
rep1(i, , n)
{
scanf("%lld", &currX);
if (i == ) s = currX;
else if (i == ) gcd = currX - lastX;
else gcd = __gcd(gcd, currX - lastX);
lastX = currX;
}
rep1(i, , m)
{
scanf("%lld", &currP);
if (!(gcd % currP)) ansPos = i;
}
if (!ansPos) puts("NO");
else printf("YES\n%lld %lld\n", s, ansPos);
return ;
}
D：
dp，然而我想的是数据结构……
dp做法是：定义一维数组f[maxn]，f[i]代表从当前位置往后取能取到的最大区间和；定义二维数组dp[2][maxn]，dp[0][i]表示从当前位置往前取能取到的最大区间和，dp[1][i]表示在乘x的情况下，从当前位置能取到的最大区间和。转移显而易见。
有个坑点是ans初始化应该是0而不是LONG_LONG_MIN
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int maxn = 3e5 + ;
ll a[maxn], f[maxn], dp[][maxn], x, ans = ;
int n; int main()
{
scanf("%d%lld", &n, &x);
rep1(i, , n) scanf("%lld", &a[i]);
f[n + ] = ;
for (int i = n; i >= ; i--)
f[i] = max(a[i], f[i + ] + a[i]);
rep1(i, , n)
{
dp[][i] = max(a[i], dp[][i - ] + a[i]);
dp[][i] = a[i] * x;
if (max(dp[][i - ], dp[][i - ]) > )
dp[][i] += max(dp[][i - ], dp[][i - ]);
ans = max(ans, max(dp[][i], dp[][i] + f[i + ]));
ans = max(ans, dp[][i]);
}
printf("%lld\n", ans);
return ;
}
E：
edu都有交互了，简直丧心病狂。看到形如a0+a1*x+a2*x^2+...+an*x^n的多项式就很自然会想到拉格朗日插值法。
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
#include <complex>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int MOD = 1e6 + ; //定义mod P意义下的运算
#include <unordered_map>
struct Mod
{
const ll mod, sqrtMod;
Mod(ll p): mod(p), sqrtMod(sqrt(p) + 0.5) {} ll add(ll a, ll b)const
{
return ((a + b) % mod + mod) % mod;
} ll mul(ll a, ll b)const
{
while (a < ) a += mod; while (b < ) b += mod;
return a * b % mod;
} ll pow(ll a, ll b)const
{
ll ret = ;
for (a %= mod; b; b >>= , a = mul(a, a))
if (b & )
ret = mul(ret, a);
return ret;
} //乘法逆元
ll inv(ll a)const
{
while (a < ) a += mod;
return pow(a, mod - );
} ll log(ll a, ll b)const
{
unordered_map<ll, ll>x;
for (ll i = , e = ; i <= sqrtMod; i++, e = mul(e, a))
{
if (!x.count(e))
x[e] = i;
}
for (ll i = , v = inv(pow(a, sqrtMod)); i <= sqrtMod; i++, b = mul(b, v))
{
if (x.count(b))
return i * sqrtMod + x[b];
}
return -;
}
} m(MOD); //拉格朗日插值法
#define X real()
#define Y imag()
class Lagrange
{
public:
static vector<ll> solve(vector<complex<ll>> p)
{
vector<ll> ret(p.size()), sum(p.size());
ret[] = p[].Y, sum[] = ;
rep0(i, , p.size())
{
for (int j = p.size() - ; j >= i; j--)
p[j].imag(m.mul(p[j].Y - p[j - ].Y, m.inv(p[j].X - p[j - i].X)));
for (int j = i; ~j; j--)
{
sum[j] = m.add(j ? sum[j - ] : , -m.mul(sum[j], p[i - ].X));
ret[j] = m.add(ret[j], m.mul(sum[j], p[i].Y));
}
}
return ret;
}
}; int main()
{
vector<complex<ll>>v;
for (ll i = , x; i < ; i++)
{
printf("? %lld\n", i);
fflush(stdout);
scanf("%lld", &x);
if (!x)
return printf("! %lld\n", i), ;
v.push_back({i, x % m.mod});
}
vector<ll> ret = Lagrange().solve(v);
for (ll i = ; i < m.mod; i++)
{
ll sum = ;
for (ll j = , x = ; j < ret.size(); j++, x = m.mul(x, i))
sum = m.add(sum, m.mul(x, ret[j]));
if (sum == )
return printf("! %lld\n", i), ;
}
puts("! -1");
return ;
}
F：
给定一个无向图，满足边双联通。要求删去尽量多的边，使得剩下的子图在包含原图所有节点的情况下仍然满足边双。输出子图。
这里给个神仙用tarjan的做法，从67行开始就有点玄幻了……
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std; const int MAXN = ; struct node
{
int v, next, use;
} edge[MAXN << ]; bool bridge[MAXN];
int low[MAXN], dfn[MAXN], vis[MAXN];
int head[MAXN], pre[MAXN], ip, sol, Count, u[MAXN], v[MAXN], n, m, p[MAXN], i, viss[MAXN], s, ans = -, j, t[MAXN]; void init(void)
{
memset(head, -, sizeof(head));
memset(vis, false, sizeof(vis));
memset(bridge, false, sizeof(bridge));
Count = sol = ip = ;
} void addEdge(int u, int v)
{
edge[ip].v = v;
edge[ip].use = ;
edge[ip].next = head[u];
head[u] = ip++;
}
bool flag;
void tarjan(int u)
{
vis[u] = ;
dfn[u] = low[u] = Count++;
for (int i = head[u]; i != -; i = edge[i].next)
{
if (!edge[i].use)
{
edge[i].use = edge[i ^ ].use = ;
int v = edge[i].v;
if (!vis[v])
{
pre[v] = u;
tarjan(v);
low[u] = min(low[u], low[v]);
if (dfn[u] < low[v])
{
sol++;
flag = ;
}
}
else if (vis[v] == )
{
low[u] = min(low[u], dfn[v]);
}
}
}
vis[u] = ;
}
int main(void)
{
scanf("%d %d", &n, &m);
for (i = ; i <= m; i++) scanf("%d %d", &u[i], &v[i]);
for (i = ; i <= m; i++) p[i] = i;
for (int jo = ; jo <= ; jo++)
{
//随机建图
for (i = ; i <= ; i++)
{
int x = rand() % m + , y = rand() % m + ;
swap(p[x], p[y]);
}
memset(viss, , sizeof(viss));
for (i = ; i <= m; i++)
{
init();
viss[i] = ;
for (j = ; j <= m; j++)
if (!viss[j])
{
addEdge(u[p[j]], v[p[j]]);
addEdge(v[p[j]], u[p[j]]);
}
flag = ;
tarjan();
for (j = ; j <= n; j++)
if (vis[j] == )
flag = ;
if (!flag)
viss[i] = ;
}
s = ;
for (i = ; i <= m; i++)
if (viss[i] == )
s++;
if (ans < s)
{
ans = s;
int y = ;
for (i = ; i <= m; i++)
if (viss[i] == )
t[++y] = p[i];
}
}
cout << m - ans << endl;
for (i = ; i <= m - ans; i++)
printf("%d %d\n", u[t[i]], v[t[i]]);
return ;
}