Preface
好久没有和队友一起打比赛了,然后今天纯战犯,G一个初值设错WA了三发还卡了1h,最后冲D也因为细节原因没调出来
但这场现场的榜只能用惨淡来形容,6题就稳Au了,而且感觉如果最后能出7个题的话甚至能有出线机会?看来还是前面题目区分度太小了
A. Best Player
签到题,按题意模拟即可
#include<cstdio>
#include<iostream>
#include<set>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=105;
int n,p[N][3],ans=-1,cs;
inline int solve(CI axis)
{
set <pi> rst; for (RI i=1;i<=n;++i)
{
pi it; if (axis==0) it=pi(p[i][1],p[i][2]);
else if (axis==1) it=pi(p[i][0],p[i][2]);
else it=pi(p[i][0],p[i][1]); rst.insert(it);
}
return rst.size();
}
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
for (j=0;j<3;++j) scanf("%d",&p[i][j]);
for (i=0;i<3;++i)
{
int tmp=solve(i); if (tmp>ans) ans=tmp,cs=i;
}
return putchar('X'+cs),0;
}
B. The Great Wall
这题我们全队给了114514种假算法,后面终于发现正确的方向才过掉
注意到这题在每一段中取\(\max-\min\)的值,其实可以看作任意取一个数乘上系数\(1\),再加上令一个数(可以和前面的相同)乘上系数\(-1\),然后再求其最大值
这样转化后由于外层套的还是个求最大值,因此我们可以直接把内层的最大值去掉来做,这样就可以比较容易地DP转移了
设\(f_{i,j,0/1/2/3}\)表示已经处理了前\(i\)个数,且已经分了\(j\)段,此时第\(j\)段的状态为:
- \(0\):既没有选乘\(1\)的,也没有选乘\(-1\)的
- \(1\):没有选乘\(1\)的,但选了乘\(-1\)的
- \(2\):选了乘\(1\)的,但没有选乘\(-1\)的
- \(3\):选了乘\(1\)的,也选了乘\(-1\)的
这样就得到一个状态数为\(O(n^2)\),转移为\(O(1)\)的DP了,可以卡过此题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4+5;
const int INF = 1e18+7;
int n, A[N];
int dp[2][N][4];
signed main(){
// freopen("1.in", "r", stdin);
scanf("%lld", &n);
for (int i=1; i<=n; ++i) scanf("%lld", &A[i]);
for (int k=0; k<4; ++k){
for (int j=0; j<=n; ++j) dp[1][j][k]=dp[0][j][k]=-INF;
}dp[0][0][0]=dp[0][0][3]=0;
for (int i=1; i<=n; ++i){
for (int j=i; j>0; --j){
int mx=0;
int cur=(i&1), lst=(cur^1);
mx = dp[lst][j-1][3];
for (int k=0; k<4; ++k) dp[cur][j][k]=-INF;
dp[cur][j][0]=max({mx, dp[lst][j][0]});
dp[cur][j][1]=max({mx-A[i], dp[lst][j][0]-A[i], dp[lst][j][1]});
dp[cur][j][2]=max({mx+A[i], dp[lst][j][0]+A[i], dp[lst][j][2]});
// printf("i=%d j=%d %d %d %d %d %d\n", i, j, mx, dp[lst][j][0], dp[lst][j][1]+A[i], dp[lst][j][2]-A[i], dp[lst][j][3]);
dp[cur][j][3]=max({mx, dp[lst][j][0], dp[lst][j][1]+A[i], dp[lst][j][2]-A[i], dp[lst][j][3]});
//for (int k=0; k<4; ++k) printf("dp[%d][%d][%d]=%d\n", i, j, k, dp[cur][j][k]);
}
}
for (int i=1; i<=n; ++i) printf("%lld\n", dp[n&1][i][3]);
return 0;
}
C. Lucky Sequence
计数题,撤退
D. Farm
思路并不难想的一个图论题,但细节还是挺多的
考虑把带有限制关系的边称为special的,我们用类似于克鲁斯卡尔求MST的过程,用并查集维护点之间的连通关系
我们可以先对于所有的special的边,将其对应两点合并
然后再对剩下的集合关系,用非special的边跑一边克鲁斯卡尔,不难发现此时选中的边一定在最后的答案中
接下来只把上面选中的边选上得到一个新图,注意到新图中连通块的数量是\(O(q)\)级别的
那么所有没选中的边其实归根到底只有\(O(q^2)\)种有意义的取值,我们把这些边保留存入集合\(E'\)中
最后来个\(O(2^q)\)枚举每个限制的情形,第\(i\)位上为\(0\)则表示钦定第\(u_i\)条边加入图中,为\(1\)则表示钦定第\(v_i\)条边加入图中
当然这样处理完强制加入的边后图可能还不连通,因此就需要对\(E'\)中的边再跑一次克鲁斯卡尔算法来使得图连通
总复杂度\(O(m\log m+2^q\times q^2)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
typedef pair <int,int> pi;
struct edge
{
int x,y,z;
friend inline bool operator < (const edge& A,const edge& B)
{
return A.z<B.z;
}
}; int n,m,q,ans,x[N],y[N],z[N],u[N],v[N],sp[N],fa[N],bel[N],rst[N],vis[N];
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void merge(CI x,CI y)
{
fa[getfa(x)]=getfa(y);
}
int main()
{
//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
scanf("%d%d%d",&x[i],&y[i],&z[i]);
for (i=1;i<=n;++i) fa[i]=i;
for (i=1;i<=m;++i) merge(x[i],y[i]);
for (i=2;i<=n;++i) if (getfa(i)!=getfa(1)) return puts("-1"),0;
for (scanf("%d",&q),i=0;i<q;++i)
scanf("%d%d",&u[i],&v[i]),sp[u[i]]=sp[v[i]]=1;
for (i=1;i<=n;++i) fa[i]=i; vector <edge> E;
for (i=1;i<=m;++i) if (sp[i]) merge(x[i],y[i]);
else E.push_back((edge){x[i],y[i],z[i]});
sort(E.begin(),E.end()); vector <edge> cs;
for (auto [x,y,z]:E)
{
if (getfa(x)==getfa(y)) continue;
cs.push_back((edge){x,y,z}); merge(x,y); ans+=z;
}
for (i=1;i<=n;++i) fa[i]=i;
for (auto [x,y,z]:cs) merge(x,y);
int idx=0; for (i=1;i<=n;++i)
{
int tmp=getfa(i); if (!rst[tmp]) rst[tmp]=++idx; bel[i]=rst[tmp];
}
map <pi,int> mp; vector <edge> left;
for (i=1;i<=m;++i) if (bel[x[i]]!=bel[y[i]])
{
int a=bel[x[i]],b=bel[y[i]];
if (!mp[pi(a,b)]) mp[pi(a,b)]=z[i];
else mp[pi(a,b)]=min(mp[pi(a,b)],z[i]);
}
for (auto [it,val]:mp)
left.push_back((edge){it.first,it.second,val});
sort(left.begin(),left.end());
int ret=1e9; for (i=0;i<(1<<q);++i)
{
for (j=1;j<=idx;++j) fa[j]=j; int cur=0;
for (j=0;j<q;++j) vis[u[j]]=vis[v[j]]=0;
for (j=0;j<q;++j) if ((i>>j)&1)
{
if (!vis[v[j]]) cur+=z[v[j]],vis[v[j]]=1; merge(bel[x[v[j]]],bel[y[v[j]]]);
} else
{
if (!vis[u[j]]) cur+=z[u[j]],vis[u[j]]=1; merge(bel[x[u[j]]],bel[y[u[j]]]);
}
for (auto [x,y,z]:left)
{
if (getfa(x)==getfa(y)) continue; merge(x,y); cur+=z;
}
ret=min(ret,cur);
}
return printf("%d",ans+ret),0;
}
E. Isomerism
什么化学阅读理解题,反正我高中选考没选化学,全靠徐神秒了
#include <bits/stdc++.h>
int T;
std::map<std::string, int> pri;
int main() {
std::ios::sync_with_stdio(false);
pri["-F"] = 1;
pri["-Cl"] = 2;
pri["-Br"] = 3;
pri["-I"] = 4;
pri["-CH3"] = 5;
pri["-CH2CH3"] = 6;
pri["-CH2CH2CH3"] = 7;
pri["-H"] = 8;
int T; std::cin >> T; while(T--) {
std::string R1, R2, R3, R4;
std::cin >> R1 >> R2 >> R3 >> R4;
if(R1 == R3 || R2 == R4) std::cout << "None\n";
else if(R1 == R2 || R3 == R4)
std::cout << "Cis\n";
else if(R1 == R4 || R2 == R3)
std::cout << "Trans\n";
else if(pri[R1] < pri[R3] && pri[R2] < pri[R4] || pri[R1] > pri[R3] && pri[R2] > pri[R4])
std::cout << "Zasamman\n";
else std::cout << "Entgegen\n";
}
return 0;
}
F. Maximize the Ratio
好神的几何题,祁神对着jiangly的题解研究了很久,反正我是一点做不来
G. Photograph
本来我是不会这个题的,但徐神告诉我链表后我马上就想到了关键,然后就会了
这题其实修改操作啥的都可以模拟,而维护贡献的过程显然可以用set
维护前驱后继来做,但这样\(10^7\)再带个\(\log\)显然是跑不过\(1s\)的时限的
考虑去掉\(\log\),这题的一个最好的性质就是我们是知道当\(n\)次操作后的最终状态的,因此不妨考虑从后往前倒着做
每次删除一个数并求前驱后继很显然可以用双向链表来维护,这样就把\(\log\)去掉了
总复杂度\(O(nq)\)
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=100005;
int n,q,h[N],p[N],tmp[N],L[N],R[N],k,all;
inline LL solve(LL ret=0)
{
RI i; for (i=1;i<=n;++i) L[i]=i-1,R[i]=i+1; R[0]=1; L[n+1]=n;
LL cur=all; for (ret=cur,i=n;i>1;--i)
{
int now=p[i],pre=L[now],nxt=R[now];
if (pre!=0) cur-=1LL*(h[now]-h[pre])*(h[now]-h[pre]);
if (nxt!=n+1) cur-=1LL*(h[now]-h[nxt])*(h[now]-h[nxt]);
if (pre!=0&&nxt!=n+1) cur+=1LL*(h[pre]-h[nxt])*(h[pre]-h[nxt]);
R[pre]=nxt; L[nxt]=pre; ret+=cur;
}
return ret;
}
signed main()
{
// freopen("G.in","r",stdin); freopen("G.out","w",stdout);
RI i; for (scanf("%lld%lld",&n,&q),i=1;i<=n;++i) scanf("%lld",&h[i]);
for (i=1;i<=n;++i) scanf("%lld",&p[i]);
for (i=1;i<n;++i) all+=1LL*(h[i]-h[i+1])*(h[i]-h[i+1]);
LL ans=solve(); printf("%lld\n",ans);
while (q--)
{
scanf("%lld",&k); k=(ans+k)%n;
for (i=1;i<=n;++i) tmp[i]=p[(i+k-1)%n+1];
for (i=1;i<=n;++i) p[i]=tmp[i];
//for (i=1;i<=n;++i) printf("%d%c",p[i]," \n"[i==n]);
ans=solve(); printf("%lld\n",ans);
}
return 0;
}
H. Absolute Space
神仙题,题目都没看
I. The Answer!
看jiangly的博客就知道这题肯定是这场的防AK题了
J. Let's Play Jigsaw Puzzles!
签到题,直接爆搜一下就好了
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int n,d[N*N][4],a[N][N];
inline void DFS(CI num,CI x,CI y)
{
if (a[x][y]) return; a[x][y]=num;
for (RI i=0;i<4;++i) if (d[num][i]!=-1)
DFS(d[num][i],x+dx[i],y+dy[i]);
}
int main()
{
//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
RI i,j; int st; for (scanf("%d",&n),i=1;i<=n*n;++i)
{
for (j=0;j<4;++j) scanf("%d",&d[i][j]);
if (d[i][0]==-1&&d[i][2]==-1) st=i;
}
for (DFS(st,1,1),i=1;i<=n;++i)
for (j=1;j<=n;++j) printf("%d%c",a[i][j]," \n"[j==n]);
return 0;
}
K. Browser Games
徐神写的字符串,我题目都没看来着
#include <bits/stdc++.h>
constexpr int $n = 2.5e6 + 5;
int go[$n][28], siz[$n], O = 1, pa[$n];
int insert(std::string &s) {
int now = 1;
for(char c: s) {
int u;
if(c == '.') u = 26; else if(c == '/') u = 27;
else u = c - 'a';
if(!go[now][u]) go[now][u] = ++O, pa[go[now][u]] = now;
now = go[now][u];
siz[now] += 1;
}
return now;
}
int ue[$n], cur[$n], fa[$n];
int father(int i) {
if(i == fa[i]) return i;
return fa[i] = father(fa[i]);
}
int main() {
// freopen("K.in", "r", stdin);
std::ios::sync_with_stdio(false);
int n; std::cin >> n;
for(int i = 1; i <= n; ++i) fa[i] = i;
for(int i = 1; i <= n; ++i) {
std::string s; std::cin >> s;
ue[i] = insert(s);
cur[ ue[i] ] = i;
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
ans += 1;
int s = ue[i];
auto unionn = [&ans] (int a, int b) {
if(!a) return b; if(!b) return a;
a = father(a), b = father(b);
if(a != b) fa[b] = a, ans -= 1;
return a;
};
while(s > 1) {
siz[s] -= 1;
if(siz[s] == 0) for(int ch: go[s]) if(ch && siz[ch] == 0)
cur[s] = unionn(cur[s], cur[ch]);
s = pa[s];
}
std::cout << ans << char(10);
}
for(int i = 1; i <= O; ++i) if(siz[i]) perror("Wcao\n");
return 0;
}
L. Sheep Village
好,又是不会的一题
M. Tower of the Sorcerer
好劲的题啊,看了好久的jiangly博客才会做,然后还被卡了精度把double
改成叉积才跑过
首先要想到最优方案的形式,一定是先不断提示自己的攻击力直到最高,然后再去杀其它的怪
因此不妨假设所有怪都是最后被杀掉的,然后考虑最小化从初始状态到最后所掉的血量
令\(f_i\)表示当前攻击力为\(i\)时,最少需要额外收到多少伤害才能把攻击力变成最大值
转移的话考虑倒推,对于攻击力为\(j(j>i)\)的怪物,设其血量为\(hp_j\),则转移为:
\[f_i=\min_{j>i} (f_j+(\lceil\frac{hp_j}{i}\rceil-\lceil\frac{hp_j}{maxatk}\rceil)\times j) \]乍一看这个转移很难优化,但有个很妙的trick就是我们直接枚举\(k=\lceil\frac{hp_j}{i}\rceil\),然后化一下后面的部分就发现我们要最小化\(k\times j+f_j-\lceil\frac{hp_j}{maxatk}\rceil\times j\)的值
不妨把\(hp_j\)看作版本号,\(j,\lceil\frac{hp_j}{maxatk}\rceil\times j\)看作一条直线的斜率和截距,那么我们查询时就是要求\(hp_j\le i\times k\)的版本中,当横坐标为\(k-1\)时,该版本中直线的纵坐标的最小值
这个就是个经典的Convex Trick,直接维护一个上凸壳然后二分查询即可,至于版本号由于这里只有前缀查询,可以给以版本号为下标用树状数组维护凸壳
总复杂度\(O(n\log^3 n)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const LL N=100005,INF=1e18;
int n,mxhp,mxatk,satk,atk[N],hp[N],f[N]; vector <int> v[N];
struct Line
{
int k,b;
inline Line(CI K=0,CI B=0)
{
k=K; b=B;
}
inline LL get(CI x)
{
return 1LL*k*x+b;
}
friend inline Line operator - (const Line& A,const Line& B)
{
return Line(A.k-B.k,A.b-B.b);
}
};
inline int Cross(const Line& A,const Line& B)
{
return A.k*B.b-A.b*B.k;
}
struct Convex
{
vector <Line> stk;
inline void insert(const Line& L)
{
while (stk.size()>1&&Cross(stk.back()-stk[stk.size()-2],L-stk.back())>=0) stk.pop_back(); stk.push_back(L);
}
inline LL query(CI x)
{
if (stk.empty()) return INF;
int l=0,r=stk.size()-1,mid; while (l<r)
{
mid=l+r>>1; if (stk[mid].get(x)<stk[mid+1].get(x)) r=mid; else l=mid+1;
}
return stk[l].get(x);
}
};
class Tree_Array
{
private:
Convex t[N];
public:
#define lowbit(x) (x&-x)
inline void add(RI x,const Line& L)
{
for (;x<=mxhp;x+=lowbit(x)) t[x].insert(L);
}
inline int get(RI x,CI y,int ret=INF)
{
for (;x;x-=lowbit(x)) ret=min(ret,t[x].query(y)); return ret;
}
#undef lowbit
}BIT;
signed main()
{
//freopen("M.in","r",stdin); freopen("M.out","w",stdout);
RI i,j; for (scanf("%lld%lld",&n,&satk),i=1;i<=n;++i)
scanf("%lld%lld",&atk[i],&hp[i]),v[atk[i]].push_back(hp[i]);
mxatk=max(satk,*max_element(atk+1,atk+n+1));
mxhp=*max_element(hp+1,hp+n+1); int ans=0;
for (i=1;i<=n;++i) ans+=(hp[i]-1)/mxatk*atk[i];
for (i=1;i<mxatk;++i) f[i]=INF;
for (i=mxatk;i>=1;--i)
{
for (j=1;;++j)
{
f[i]=min(f[i],BIT.get(min(i*j,mxhp),j-1));
if (i*j>mxhp) break;
}
for (auto x:v[i]) BIT.add(x,Line(i,f[i]-(x-1)/mxatk*i));
}
return printf("%lld",ans+f[satk]),0;
}
Postscript
连训三天爽歪歪
标签:std,now,const,cur,Contest,int,Regional,Programming,include From: https://www.cnblogs.com/cjjsb/p/17840797.html