Preface
牢闪又双叒叕红温了，被 B 题一个边界卡了 2h 不出题
虽然后面慢慢出题把排名打回来了，但因为时间被浪费了太多导致会的 J 题没时间写了，又成大战犯了
A. chmod
签到题，我题意都没看
#include <bits/stdc++.h>
char s[4] = "rwx";
int main() {
int T; scanf("%d", &T); while(T--) {
int a[3];
for(int i = 0; i < 3; ++i) {
scanf("%1d", a + i);
for(int j = 0; j < 3; ++j) {
printf("%c", (a[i] >> (2 - j) & 1) ? s[j] : '-');
}
}
printf("\n");
}
}
B. Expression Matrix
赤石构造题，有人把符号构造到外面一圈了然后一直 WA 我不说是谁
大致思路就是 \(n,m\) 均为偶数时贪心地全用 * 构造，可以保证每行每列都是 \(11\) （除了周围一圈外）
否则考虑令 \(m\) 为奇数，如果用上述的方法构造会在某些行出现 \(11\times 11\) 这样的情况，需要强行将其中一个乘号改成加号
这里还要根据 \(n\) 的奇偶性讨论，若 \(n\) 为偶数则列没有特别的限制，可以钦定所有的加号都在同一列上；否则还需要满足若干行列都要有加号，要斜着构造才行
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=10;
int n,m; char a[N][N];
int main()
{
scanf("%d%d",&n,&m);
int swaped=0;
if (n%2==0&&m%2==0)
{
for (RI i=1;i<=n;++i) a[i][1]=a[i][m]='1';
for (RI j=1;j<=m;++j) a[1][j]=a[n][j]='1';
for (RI i=2;i<n;++i)
if (i%2==0)
{
for (RI j=2;j<m;++j) a[i][j]=(j%2?'1':'*');
} else
{
for (RI j=2;j<m;++j) a[i][j]=(j%2?'*':'1');
}
} else
{
if (m%2==0) swap(n,m),swaped=1;
for (RI i=1;i<=n;++i) a[i][1]=a[i][m]='1';
for (RI j=1;j<=m;++j) a[1][j]=a[n][j]='1';
for (RI i=2;i<n;++i)
if (i%2==0)
{
for (RI j=2;j<m;++j) a[i][j]=(j%2?'1':'*');
} else
{
for (RI j=2;j<m;++j) a[i][j]=(j%2?'*':'1');
}
if (n%2==1)
{
for (RI i=3,j=3;i<max(n,m);i+=2)
{
if (i<n&&i<m) a[i][i]='+';
else if (i<n)
{
if (i<n&&j<m)
{
a[i][j]='+'; j+=2;
if (j>=m) j=3;
}
} else
{
if (j<n&&i<m)
{
a[j][i]='+'; j+=2;
if (j>=n) j=3;
}
}
}
} else
{
if (m>3)
for (RI i=3;i<n;i+=2) a[i][3]='+';
}
}
if (swaped)
{
for (RI i=1;i<=m;++i,putchar('\n'))
for (RI j=1;j<=n;++j) putchar(a[j][i]);
} else
{
for (RI i=1;i<=n;++i,putchar('\n'))
for (RI j=1;j<=m;++j) putchar(a[i][j]);
}
}
C. Seats
套路题，不难想到 \(i\to a_i\) 连边，得到的是基环内向森林
若一个连通块内有环，则其贡献为环的大小；否则找一个以 \([n+1,2n]\) 的点为终点的最长路即可
拓扑排序很容易求解
#include<cstdio>
#include<iostream>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,a[N],deg[N],f[N];
int main()
{
scanf("%d",&n);
for (RI i=1;i<=n;++i) scanf("%d",&a[i]),++deg[a[i]];
queue <int> q; int ans=2*n;
for (RI i=1;i<=2*n;++i) if (!deg[i]) q.push(i);
while (!q.empty())
{
int now=q.front(); q.pop(); --ans;
if (now>n) { ans+=f[now]; continue; }
f[a[now]]=max(f[a[now]],f[now]+1);
if (--deg[a[now]]==0) q.push(a[now]);
}
return printf("%d",ans),0;
}
D. Double Subsequence
神秘 DP 题，被徐神轻松 solo 了
考虑若存在一个极小的区间 \([l,r]\)，使得这个区间中 \(s_1,s_2\) 都作为子序列出现过，那么所有包含 \([l,r]\) 的区间都可以统计，贡献为 \(l\times (n-r+1)\)
考虑 DP，令 \(f_{i,j,k}\) 表示处理了前 \(i\) 个位置，\(s_1\) 匹配了前 \(j\) 个字符，\(s_2\) 匹配了前 \(k\) 个字符，极小区间的左端点之和
转移比较显然，但最后统计答案时要用 \(f_{i,\star,\star}-f_{i-1,\star,\star}\) 来得到强制以 \(i\) 为右端点的答案
复杂度 \(O(|S|\times|s_1|\times |s_2|)\)
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr llsi mod = 998244353;
int n, l1, l2;
char S[100005], s1[25], s2[25];
int dp[100001][21][21];
inline void add(int &a, const int &b) {
if((a += b) >= mod) a -= mod;
}
inline void sub(int &a, const int &b) {
if((a -= b) < 0) a += mod;
}
int main() {
scanf("%s%s%s", S + 1, s1 + 1, s2 + 1);
n = strlen(S + 1);
l1 = strlen(s1 + 1);
l2 = strlen(s2 + 1);
for(int i = 1; i <= n; ++i) {
add(dp[i][0][1], dp[i - 1][0][1]);
add(dp[i][1][0], dp[i - 1][1][0]);
add(dp[i][1][1], dp[i - 1][1][1]);
if(S[i] == s1[1]) add(dp[i][1][0], i), add(dp[i][1][1], dp[i - 1][0][1]);
if(S[i] == s2[1]) add(dp[i][0][1], i), add(dp[i][1][1], dp[i - 1][1][0]);
if(S[i] == s1[1] && S[i] == s2[1]) add(dp[i][1][1], i);
}
for(int i = 1; i <= n; ++i) for(int j = 2; j <= l1; ++j) {
add(dp[i][j][0], dp[i - 1][j][0]);
if(S[i] == s1[j]) add(dp[i][j][0], dp[i - 1][j - 1][0]);
}
for(int i = 1; i <= n; ++i) for(int j = 2; j <= l2; ++j) {
add(dp[i][0][j], dp[i - 1][0][j]);
if(S[i] == s2[j]) add(dp[i][0][j], dp[i - 1][0][j - 1]);
}
for(int i = 1; i <= n; ++i) for(int j = 1; j <= l1; ++j) for(int k = 1; k <= l2; ++k) if(j + k > 2) {
add(dp[i][j][k], dp[i - 1][j][k]);
if(S[i] == s1[j]) add(dp[i][j][k], dp[i - 1][j - 1][k]);
if(S[i] == s2[k]) add(dp[i][j][k], dp[i - 1][j][k - 1]);
if(S[i] == s1[j] && S[i] == s2[k]) add(dp[i][j][k], dp[i - 1][j - 1][k - 1] % mod);
}
// for(int i = 1; i <= n; ++i) printf("%d%c", dp[i][1][1], i == n ? 10 : 32);
int ans = 0;
for(int i = n; i >= 0; --i) {
sub(dp[i][l1][l2], dp[i - 1][l1][l2]);
add(ans, llsi(dp[i][l1][l2]) * llsi(n - i + 1) % mod);
}
printf("%d\n", ans);
return 0;
}
E. Trade Road
徐神手玩发现如果存在 \(A\to B\) 的边，则剩下的所有点要么都指向 \(A\)，要么都指向 \(B\)
但有且仅有一种情况特例，即 \(A\) 存在两个最远点 \(B,C\)，且 \(B\) 的最远点为 \(C\)，则可以形成一个等腰三角形，简单特判这种情况即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int k, n;
set<int> st[N], dist[N];
map<int, int> bkt;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> k >> n;
vector<int> A(2*n);
for (int i=0; i<n; ++i) cin >> A[i], --A[i];
for (int i=n; i<2*n; ++i) A[i]=A[i-n];
auto calc = [&](int x, int y){return min(abs(y-x), k-abs(y-x));};
for (int i=0, j=0; i<n; ++i){
while (calc(A[i], A[j]) < calc(A[i], A[j+1])){
// printf("i=%d j=%d calc(i, j)=%d calc(i, j+1)=%d\n", i, j, calc(A[i], A[j]), calc(A[i], A[j+1]));
++j;
}
st[i].insert(j%n); st[j%n].insert(i); dist[i].insert(j%n);
if (calc(A[i], A[j]) == calc(A[i], A[j+1])){
st[i].insert((j+1)%n); st[(j+1)%n].insert(i); dist[i].insert((j+1)%n);
}
}
// for (int i=0; i<n; ++i){
// printf("i=%d:", i); for (int x : st[i]) printf("%d ", x); puts("");
// }
int ans=0;
for (int i=0; i<n; ++i) ans = max(ans, (int)st[i].size());
for (int i=0; i<n; ++i) if (dist[i].size()==2){
int x=*dist[i].begin(), y = *dist[i].rbegin();
if (dist[x].count(y) || dist[y].count(x)) ans=max(ans, 3);
}
cout << ans << '\n';
return 0;
}
F. Try a try, AC is OK
仔细阅读题目发现不要求选的两个下标不同，因此找最大数输出即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,x;
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n); int mx=0;
for (RI i=1;i<=n;++i) scanf("%d",&x),mx=max(mx,x);
printf("%d\n",mx);
}
return 0;
}
G. Disappearing Number
签到题，不难发现此时每个数大致可以看成 \(9\) 进制下的，只不过有一个数码不能使用，简单模拟下即可
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,n,x,w[10];
signed main()
{
for (scanf("%lld",&t);t;--t)
{
scanf("%lld%lld",&n,&x);
for (RI i=0;i<10;++i) w[i]=(i==x?0:1);
for (RI i=1;i<10;++i) w[i]+=w[i-1];
int rk=0; vector <int> vec;
while (n>0) vec.push_back(n%10),n/=10;
reverse(vec.begin(),vec.end());
for (auto x:vec) rk=rk*9+(x==0?0:w[x-1]);
printf("%lld\n",rk+1);
}
return 0;
}
H. Maximum Flow
防 AK 论文题，直接弃疗
I. Prime Guess I
神秘数列交互题，徐神赛时想了很久还是不会，那我当然是不补了
J. Prime Guess II
一顿观察后发现是个经典的维护凸包题，但由于我赛时太唐了把时间浪费完了然后祁神没时间写了，只能说全责
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = (int)2e7+5;
using pii = pair<int, int>;
#define ft first
#define sd second
const int N = 1e6+5;
int pri[N], phi[N], sd[N], totp;
int n, q, A[N], K[N], C[N];
pii stk[N]; int top;
vector<pii> qry[N];
pii ans[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
phi[1]=sd[1]=1;
for (int i=2; i<N; ++i){
if (!phi[i]) pri[++totp]=i, phi[i]=i-1, sd[i]=i+1;
for (int j=1; j<=totp&&i*pri[j]<N; ++j){
int k = i*pri[j];
if (i%pri[j]){
phi[k] = phi[i]*(pri[j]-1);
sd[k] = sd[i]*(pri[j]+1);
}else{
phi[k] = phi[i]*pri[j];
sd[k] = sd[i] + 1LL*pri[j]*(sd[i]-sd[i/pri[j]]);
}
}
}
// printf("phi:"); for (int i=1; i<=10; ++i) printf("%lld ", phi[i]); puts("");
// printf("sd:"); for (int i=1; i<=10; ++i) printf("%lld ", sd[i]); puts("");
cin >> n >> q;
for (int i=1; i<=n; ++i){
cin >> A[i];
K[i] = K[i-1]+phi[A[i]];
C[i] = C[i-1]+sd[A[i]]*A[i];
}
// printf("K:"); for (int i=1; i<=n; ++i) printf("%lld ", K[i]); puts("");
// printf("C:"); for (int i=1; i<=n; ++i) printf("%lld ", C[i]); puts("");
for (int i=1; i<=q; ++i){
int u, l; cin >> u >> l;
qry[l].emplace_back(u, i);
}
auto check = [&](int id, int x){return x*K[id]-C[id];};
for (int i=n; i>0; --i){
// printf("i=%lld:", i+1); for (int j=1; j<=top; ++j) printf("(%lld %lld)", stk[j].ft, stk[j].sd); puts("");
while (top>0 && check(stk[top].ft, stk[top].sd) < check(i, stk[top].sd)) --top;
if (0==top){
stk[++top] = {i, INF};
}else{
int L=0, R=stk[top].sd;
while (L<R){
int M=L+(R-L)/2+1;
if (check(stk[top].ft, M) <= check(i, M)) L=M;
else R=M-1;
}
stk[++top] = {i, L};
}
for (auto [u, id] : qry[i]){
int l = i;
int valL = u*K[l-1]-C[l-1];
int L=1, R=top;
while (L<R){
int M=L+(R-L)/2+1;
if (stk[M].sd >= u) L=M;
else R=M-1;
}
int valR = u*K[stk[R].ft]-C[stk[R].ft];
ans[id] = {valR-valL, stk[R].ft};
}
}
// printf("i=%lld:", 1LL); for (int j=1; j<=top; ++j) printf("(%lld %lld)", stk[j].ft, stk[j].sd); puts("");
for (int i=1; i<=q; ++i) cout << ans[i].ft << ' ' << ans[i].sd << '\n';
return 0;
}
K. Lethal Company
神秘贪心题，想到二分转为判定性问题就很简单了
考虑二分答案 \(lim\)，检验是否可以存活到 \(lim\) 时刻，显然此时只要关心那些能在 \(lim\) 时刻之前到达人所在的位置的怪即可
不难发现可以对每个怪求出一个值表示至少需要看几次，显然我们倒着分配时间，优先看 \(t_i\) 较大的怪一定最优
注意可能会出现某一时刻有多个怪物在同一通道的情况，因此需要对每个通道分别记录之前已经看了多久
总复杂度 \(O((n+m)\log t)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
const int N=500005,INF=4e18;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
char Fin[S],*A,*B;
public:
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
#undef tc
}F;
struct ifo
{
int t,x,y;
inline ifo(CI T=0,CI X=0,CI Y=0)
{
t=T; x=X; y=Y;
}
friend inline bool operator < (const ifo& A,const ifo& B)
{
return A.t>B.t;
}
}a[N]; int n,m,k,bkt[N];
inline bool check(CI lim)
{
for (RI i=1;i<=n;++i) bkt[i]=0;
int rem=lim;
for (RI i=1;i<=m;++i)
{
int looks=lim+2-a[i].t-(a[i].y+k-1)/k;
if (looks>0)
{
looks-=bkt[a[i].x];
if (looks>0)
{
rem-=looks;
if (rem+1<a[i].t) return 0;
bkt[a[i].x]+=looks;
}
}
}
return 1;
}
signed main()
{
F.read(n); F.read(m); F.read(k);
for (RI i=1;i<=m;++i)
F.read(a[i].t),F.read(a[i].x),F.read(a[i].y);
sort(a+1,a+m+1);
int l=0,r=INF+5,mid,ret;
while (l<=r)
if (check(mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
if (ret>INF) puts("-1"); else printf("%lld\n",ret);
return 0;
}
L. Chess
神秘找规律
手玩 \(k=2,3\) 的 SG 函数会发现当 \(k\nmid x\) 时这个 \(k\) 就是先手必胜的，反之后手必胜
直接从小到大暴力枚举 \(k\) 检验，不难发现最多枚举 \(\log x\) 级别就能找到一个 \(k\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,x;
signed main()
{
for (scanf("%lld",&t);t;--t)
{
scanf("%lld",&x); int ans;
for (RI i=2;;++i) if (x%i!=0) { ans=i; break; }
printf("%lld\n",ans);
}
return 0;
}
M. Window Decoration
签到题，我题意都不知道
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
set<pii> st;
int n;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
int ans=0;
for (int i=1; i<=n; ++i){
int x, y; cin >> x >> y;
if (st.count({x, y})) continue;
st.insert({x, y});
ans += 4;
if (st.count({x-1, y})) --ans;
if (st.count({x+1, y})) --ans;
if (st.count({x, y-1})) --ans;
if (st.count({x, y+1})) --ans;
}
if (ans%2==0) cout << ans/2 << '\n';
else cout << ans/2 << ".5\n";
return 0;
}
Postscript
经典三人被可可一人 \(n+1\) 暴打，不用说都知道是谁的问题
标签：Provincial,const,Contest,int,2024,ans,include,RI,define From： https://www.cnblogs.com/cjjsb/p/18351455