ICPC2023 济南站 个人题解
和队友都干了!5题665罚时银尾()
A
注意到原题有保证给定的任意括号序列都对应着至少一个合法括号序列,回顾一下判定一个括号序列是否合法的过程:我们发现我们使用一个栈来判定一个括号序列是否可以是一个合法的括号序列。把左括号看成+1,右括号看成-1,那么同一种括号任意位置的前缀和显然都
然后我们考虑,在改变左右方向的括号序列里面,实际上只需要如果连续有四个相同种类的括号,那么就至少有两种方法可以保证合法:(())
与 ()()
进一步发现,其实只要存在任意三个位置有相同括号就可以了。因为多一种括号只需要考虑形如 (([]))
的情况,这样的情况显然可以通过变成 ()[]()
来判定。
因为这个题目限制保证了你是合法的括号序列,所以在后面肯定也有一个括号可以和多的这个左括号匹配。因此这个题就转变成了是否能找到三个相同的位置有相同类型括号即可。时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
const int N = 1e5 + 10;
char s[N];
int n;
void solve() {
cin >> s;
n = strlen(s);
for (int i = 0;i < n;++i) {
if (s[i] == ')') s[i] = '(';
if (s[i] == ']') s[i] = '[';
}
int cnt = 0;
for (int i = 0;i < n-1;++i) {
if (s[i] == s[i+1]) ++cnt;
}
if (cnt > 2) puts("No");
else puts("Yes");
}
signed main() {
ios::sync_with_stdio(false);
int T;cin >> T;
while (T--) solve();
return 0;
}
B
先考虑一个简单的树形 DP:我们令
for (int i = 0;i <= k+1;++i) tmp[i] = 0;
for (int j = 0;j <= min(siz[y],k);++j) {//这一步的上界为k,因为i要占用1个点
for (int i = min(k+1 - j,siz[x]);i >= 1;--i) {
tmp[i+j] = (tmp[i+j] + dp[x][i] * dp[y][j] % mod) % mod;
}
}
siz[x] += siz[y];
for (int i = 0;i <= k+1;++i) dp[x][i] = tmp[i];
unordered_map
来存这个东西。
考虑如何划分这个
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
const int N = 1e5 + 10;
const int K = 700;
const ll mod = 998244353;
unordered_map <int,ll> DP[N],ttmp;
ll dp[N][K],n,k,tmp[N],siz[N];
vector <int> G[N];
void dfs1(int x,int fa) {
dp[x][1] = 1;
siz[x] = 1;
for (auto y : G[x]) {
if (y == fa) continue;
dfs1(y,x);
for (int i = 0;i <= k+1;++i) tmp[i] = 0;
for (int j = 0;j <= min(siz[y],k);++j) {//这一步的上界为k,因为i要占用1个点
for (int i = min(k+1 - j,siz[x]);i >= 1;--i) {
tmp[i+j] = (tmp[i+j] + dp[x][i] * dp[y][j] % mod) % mod;
}
}
siz[x] += siz[y];
for (int i = 0;i <= k+1;++i) dp[x][i] = tmp[i];
}
dp[x][0] = (dp[x][k] + dp[x][k+1]) % mod;
/*cout << "nowpoi:" << x << "\n";
for (int i = 0;i <= k+1;++i) {
cout << dp[x][i] << " ";
}
cout <<"\n";*/
}
void dfs2(int x,int fa) {
DP[x][1] = 1;
siz[x] = 1;
for (auto y : G[x]) {
if (y == fa) continue;
dfs2(y,x);
ttmp.clear();
for (auto [j,val2] : DP[y]) {
for (auto [i,val1] : DP[x]) {
if (i + j > k+1) continue;
ttmp[i+j] = (ttmp[i+j] + val1 * val2 % mod) % mod;
}
}
DP[x].clear();
for (auto [i,val1] : ttmp) DP[x][i] = val1;
siz[x] += siz[y];
}
ll now = 0;
if (DP[x].count(k)) now = (now + DP[x][k]) % mod;
if (DP[x].count(k+1)) now = (now + DP[x][k+1]) % mod;
DP[x][0] = (now % mod + mod )% mod;
if (!DP[x][0]) DP[x].erase(0);
/*cout << "nowpoi:" << x <<"\n";
for (auto [i,j] : DP[x]) {
cout << i << " " << j << "\n";
}
cout <<"\n";*/
for (auto y : G[x]) {
if (y == fa) continue;
DP[y].clear();
}
}
void solve() {
cin >> n >> k;
for (int i = 1;i <= n;++i) G[i].clear();
for (int i = 1;i < n;++i) {
int x,y;cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
int lim = sqrt(n);
if (k <= lim) {
for (int i = 1;i <= n;++i) {
for (int j = 0;j <= k + 1;++j) {
dp[i][j] = 0;
}
}
dfs1(1,0);
cout << dp[1][0] << "\n";
} else {
DP[1].clear();
dfs2(1,0);
cout << DP[1][0] << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
int T;cin >> T;
while (T--) solve();
return 0;
}
/*
2
4 3
1 2
1 3
2 4
4 3
1 2
1 3
2 4
*/
D
签到题,我们研究一下容易发现只要存在一个
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
int calc(int x) {
int bit = 0;
while (x) {
bit = max(bit,x % 10);
x /= 10;
}
return bit;
}
void solve() {
int l1,r1,l2,r2;cin >> l1 >> r1 >> l2 >> r2;
int maxdel = max(r1-l1+1,r2-l2+1);
int ans = 0;
if (maxdel >= 10) {
ans = 9;
} else {
for (int i = l1;i <= r1;++i) {
for (int j = l2;j <= r2;++j) {
ans = max(ans,calc(i+j));
}
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
int T;cin >> T;
while (T--) solve();
return 0;
}
E
先吐槽一下,其实我不明白为什么这个题的范围要给到
我们先考虑对于一组确定的最大匹配,添加哪些边可以使得匹配数恰好 +1?记
那么就考虑如何统计
时间复杂度大概是
#include <bits/stdc++.h>
using namespace std;
//sb codeforces
#define ll long long
#define pii pair <int,int>
const int M = 1e6 + 10;
const int N = 4e5 + 10;
struct edge {
int to;
int cap;
}e[M];
int n,m,s,t,cnt = -1;
vector <int> g[N];
int cur[N],h[N];
bool vis[N];
bool bfs(int s,int t) {
for (int i = 1;i <= 2*n+2;++i) h[i] = -1;
//h.assign(2*n+10,-1);
queue <int> que;
h[s] = 0;
que.push(s);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (int i : g[u]) {
auto [v,c] = e[i];
if (c > 0 && h[v] == -1) {
h[v] = h[u] + 1;
if (v == t) return 1;
que.push(v);
}
}
}
return false;
}
int dfs(int u,int t,int f) {
if (u == t) {
return f;
}
auto r = f;
for (int &i = cur[u];i < int(g[u].size());++i) {
const int j = g[u][i];
auto [v,c] = e[j];
if (c > 0 && h[v] == h[u] + 1) {
auto a = dfs(v,t,min(r,c));
e[j].cap -= a;
e[j^1].cap += a;
r -= a;
if (!r) return f;
}
}
return f - r;
}
void addedge(int u,int v,int c) {
g[u].push_back(++cnt);
e[cnt].to = v,e[cnt].cap = c;
g[v].push_back(++cnt);
e[cnt].to = u,e[cnt].cap = 0;
}
int maxflow(int s,int t) {
int ans = 0;
while (bfs(s,t)) {
for (int i = 1;i <= 2 * n + 2;++i) cur[i] = 0;
//cout << ans << "\n";
ans += dfs(s,t,numeric_limits<int>::max());
}
return ans;
}
ll ans[2];
void dfs1(int x,int typ) {
if (typ) {
if (x <= n) ++ans[0];
} else {
if (x > n && x <= 2 * n) ++ans[1];
}
vis[x] = 1;
//cout << x << " " << typ << "\n";
for (int i : g[x]) {
auto [v,c] = e[i];
if (!vis[v] && c == typ) {
//cout << x << " " << v << endl;
dfs1(v,typ);
}
}
}
void solve() {
cin >> n >> m;
cnt = -1;
for (int i = 1;i <= 2 * n + 2;++i) vis[i] = 0,g[i].clear();
//vis.assign(2 * n+10,0);
s = 2 * n + 1,t = 2 * n + 2;
//g.resize(2*n+10);
ans[0] = ans[1] = 0;
//e.clear();
//g.clear();
//cur.clear();
//h.clear();
for (int i = 1;i <= m;++i) {
int x,y;cin >> x >> y;
addedge(x,y+n,1);
}
for (int i = 1;i <= n;++i) addedge(s,i,1);
for (int i = 1;i <= n;++i) addedge(i+n,t,1);
maxflow(s,t);
dfs1(s,1);
dfs1(t,0);
cout << (ll)ans[0] * ans[1] <<endl;
//cout << ans[0] << "ans" << ans[1] << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while (T--) solve();
return 0;
}
G
分析每一列,显然每一列至多只能有两个 1,否则为非法情况,答案为 0.
接下来考虑维护行和行之间的翻转关系,显然只有两种:
i,j 必须一起翻转,此时为s_{i,p} = s_{j,c-p+1} 即二者有一个位置在对称后都为 1 的情况。i,j 必须一个翻转时,另一个不翻转,也就是s_{i,p} = s_{j,p} ,即二者有一个位置都为 1 的情况。
对于每一行,我们考虑使用
对于关系 1,我们让
对于关系 2,我们让
最后当且仅当
时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
#define endl '\n'
const int N = 2e6 + 10;
const ll mod=1e9+7;
vector <vector<int> > a;
int r,c;
char s[N];
int ck[N],tmp[N];
int p[N];
int find(int x){
if(x!=p[x]){
p[x]=find(p[x]);
}
return p[x];
}
ll qsm(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void U(int a,int b){
if(a!=b){
p[a]=b;
}
}
void solve() {
cin >> r >> c;
a.clear();
for(int i=0;i<=2*r;i++){
p[i]=i;
}
for(int i=0;i<=c;i++){
ck[i]=tmp[i]=0;
}
a.resize(r+1);
string pz;
for (int i = 1;i <= r;++i) {
cin >> s;
a[i].resize(c+1);
for (int j = 0;j < c;++j) {
a[i][j+1] = s[j] - '0';
}
}
for(int i=1;i<=c;i++){
int cnt=0;
for(int j=1;j<=r;j++){
if(a[j][i]==1)cnt++;
if(a[j][c-i+1]==1)cnt++;
}
if(cnt>2){
cout<<0<<endl;
return;
}
}
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
tmp[j]=ck[j];
}
for(int j=1;j<=c;j++){
int x=j,y=c-j+1;
if(y!=x&&a[i][j]&&tmp[y]){
int pd1=tmp[y];
int px=find(i),py=find(pd1);
int px1=find(i+r),py1=find(pd1+r);
if(px==py1||py==px1){
cout<<0<<endl;
return;
}
U(px,py);
U(px1,py1);
}else if(a[i][j]&&tmp[j]){
int pd1=tmp[j];
int px=find(i),py=find(pd1);
int px1=find(i+r),py1=find(pd1+r);
if(px==px1||py==py1||px==py){
cout<<0<<endl;
return;
}
U(px,py1);
U(py,px1);
}
if(a[i][j])ck[j]=i;
}
}
int cnt=0;
for(int i=1;i<=2*r;i++){
int pi=find(i);
if(pi==i)cnt++;
}
cnt/=2;
cout<<qsm(2,cnt)<<endl;
}
signed main() {
ios::sync_with_stdio(false);
int T;cin >> T;
while (T--) solve();
return 0;
}
K
神仙队友秒开,被我的对顶堆板子命名给坑了。这并不好笑.jpg
首先,对于题目这种公差为 1 的等差数列,我们有一个经典的处理即
接下来考虑原题就变成了要把
所以我们考虑维护一个滑动窗口,每次把 std::multiset
来维护即可。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
const int N = 5e5 + 10;
ll n,k,a[N];
int judge(int x,int y) {
if (x > y) {
return x-y;
}
else {
return y-x;
}
}
void solve() {
cin >> n >> k;
multiset <ll> xgd;
multiset <ll,greater <ll>> bgd;
for (int i = 1;i <= n;++i) cin >> a[i];
for (int i = 1;i <= n;++i) a[i] -= i;
//bgd.insert(0);
ll s1 = 0,s2 = 0;
int L = 1;
int ans = 1;
for (int i = 1;i <= n;++i) {
if (bgd.empty()) {
xgd.insert(a[i]);
s2 += a[i];
} else {
if (a[i] > *bgd.begin()) xgd.insert(a[i]),s2 += a[i];
else bgd.insert(a[i]),s1 += a[i];
}
while (judge(bgd.size(),xgd.size()) > 1) {
if (bgd.size() > xgd.size()) {
ll x = *bgd.begin();
s2 += x;s1 -= x;
xgd.insert(x);bgd.erase(bgd.begin());
} else {
ll x = *xgd.begin();
s1 += x;s2 -= x;
bgd.insert(x);xgd.erase(xgd.begin());
}
}
//s1 bgd s2 xgd
ll val1 = 0;
if (bgd.size() >= xgd.size()) {
val1 = *bgd.begin();
} else {
val1 = *xgd.begin();
}
/*cout <<"bgd:\n";
for (auto x : bgd) cout << x << " ";
cout <<"\ndgd:\n";
for (auto x : xgd) cout << x << " ";
cout << "\n";
cout << i << ":" << val1 << "\n";*/
ll ans1 = s2 - val1 * xgd.size() + val1 * bgd.size() - s1;
//cout << i << " ans=" << ans1 << "\n";
if (ans1 > k) {
bool flag = 0;
if (bgd.find(a[L]) != bgd.end()) {
flag = 1;
bgd.erase(bgd.find(a[L]));
s1 -= a[L];
}
if (!flag) {
if (xgd.find(a[L]) != xgd.end()) {
flag = 1;
xgd.erase(xgd.find(a[L]));
s2 -= a[L];
}
}
++L;
} else {
ans = max(ans,(int)(bgd.size() + xgd.size()));
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
int T;cin >> T;
while (T--) solve();
return 0;
}
M
场上开出来的简单计算几何题,可惜机时不太够了。
我们先把凸包求出来,然后考虑枚举不在凸包上的每个点。对于一个点
时间复杂度 atan2
被卡了?学习了一个老哥的奇妙极角排序,大概也是利用叉乘但是因为整点,少了很多分类讨论()
/*
Undo the destiny.
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
int v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const ll mod = 998244353;
const double eps = 1e-10;
const int N = 2e3 + 10;
int dcmp(double a) {return a < -eps ? -1 : (a > eps ? 1 : 0);}
struct point {
double x,y;point(int X = 0,int Y = 0) {x = X,y = Y;}
friend point operator - (const point &a,const point &b) {
point c;
c.x = a.x - b.x;
c.y = a.y - b.y;
return c;
}
friend double operator ^ (const point &a,const point &b) {
return a.x * b.y - a.y * b.x;
}
}p[N],O;
bool cmp1(point a,point b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int convexhull(point *P,int n,int *cp) {
sort(P+1,P+n+1,cmp1);
int t = 0;
for (int i = 1;i <= n;++i) {
while (t > 1 && dcmp(((P[cp[t]] - P[cp[t-1]]) ^ (P[i] - P[cp[t-1]]))) <= 0) --t;
cp[++t] = i;
}
int st = t;
for (int i =n-1;i >= 1;--i) {
while (t > st && dcmp(((P[cp[t]] - P[cp[t-1]]) ^ (P[i] - P[cp[t-1]]))) <= 0) --t;
cp[++t] = i;
}
return --t;
}
int n,cp[N];
bool vis[N];
double theta(point a) {return atan2(a.y,a.x);}
bool lt(double a, double b) { return a - b < -eps; } // <
void psort(vector <int> &ps, point c) // 极角排序
{
sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
return dcmp((p[p1] - c) ^ (p[p2]-c)) > 0;
//return lt(theta(p[p1] - c), theta(p[p2] - c));
});
}
signed main() {
//FO(test)
read(n);
for (int i = 1;i <= n;++i) read(p[i].x,p[i].y);
int siz = convexhull(p,n,cp);
/*
for (int i = 1;i <= siz;++i) {
cout << p[cp[i]].x << " " << p[cp[i]].y << endl;
}
*/
for (int i = 1;i <= siz;++i) vis[cp[i]] = 1;
ll ans = 1;
for (int x = 1;x <= n;++x) {
if (vis[x]) continue;
vector <int> qwq;
for (int i = 1;i <= n;++i) {
if (i != x) qwq.push_back(i);
}
psort(qwq,p[x]);
int sz = qwq.size();
if (vis[qwq[0]] && vis[qwq[sz-1]])++ans;
for (int i = 1;i < sz;++i) {
if (vis[qwq[i]] && vis[qwq[i-1]])++ans;
}
}
cout <<ans;
return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。