Preface
来场我最爱的SUA的题，而且恰逢南京站因此袋鼠题懂得都懂
然而好家伙点开题目一看怎么全是OP题，我们队没一个玩原的这下大输特输了
因此这场前中期可以说是崩完了，一个签到因为没判\(n=1\)从20min挂到150min，除此之外其它题目基本上都要挂上三四发
不过好在最后20min连着过了卡着的DJ，最后成功以7题垫底罚时苟进金尾区
顺便提一嘴现在CF的评测机是真离谱，这场好多题从读入就开始卡常，我直接人麻了
A. Oops, It’s Yesterday Twice More
袋鼠题version3.0，但变成签到力
考虑先用\(2(n-1)\)步把所有袋鼠移动到某个角落节点上，同时要满足这个角落节点到目标节点的曼哈顿距离\(\le n-1\)
不难发现四个角落节点必有一个符合要求，逐次检验即可
#include <bits/stdc++.h>
int n, x, y;
int main() {
std::cin >> n >> x >> y;
std::swap(x, y);
std::string s = "";
if(x <= n / 2) for(int i = 1; i < n; ++i) s += "L";
else for(int i = 1; i < n; ++i) s += "R";
if(y <= n / 2) for(int i = 1; i < n; ++i) s += "U";
else for(int i = 1; i < n; ++i) s += "D";
if(x <= n / 2) for(int i = 1; i < x; ++i) s += "R";
else for(int i = n; i > x; --i) s += "L";
if(y <= n / 2) for(int i = 1; i < y; ++i) s += "D";
else for(int i = n; i > y; --i) s += "U";
std::cout << s << std::endl;
return 0;
}
B. Puzzle in Inazuma
看通过人数可知这题不可做
C. Klee in Solitary Confinement
好家伙\(10^6\)的数据差点给我\(O(n)\)做法卡TLE了，真牛魔的惊险
首先不难发现最后的众数一定是原来序列中出现过的数，因此我们可以枚举最后变成的数\(x\)
考虑当我们的区间覆盖到值为\(x-k\)的数时，贡献会加\(1\)；而覆盖到值为\(x\)的数时，贡献为减\(1\)；对于其它数则没有影响
我们可以把所有值相同的位置用vector存起来，然后每次将\(x-k,x\)对应的vector归并后，跑一个最大子段和即可得到最优的增量
注意特判\(k=0\)的情形，总复杂度\(O(n)\)
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5,S=1e6;
int n,k,a[N]; vector <int> pos[N<<1];
inline vector <int> merge(vector <int>& A,vector <int>& B)
{
vector <int> C; RI i=0,j=0;
while (i<A.size()&&j<B.size())
if (A[i]<B[j]) ++i,C.push_back(-1); else ++j,C.push_back(1);
while (i<A.size()) ++i,C.push_back(-1);
while (j<B.size()) ++j,C.push_back(1);
return C;
}
int main()
{
RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)
scanf("%d",&a[i]),pos[a[i]+S].push_back(i);
int ans=0; for (RI i=-S;i<=S;++i) ans=max(ans,(int)pos[i+S].size());
if (k==0) return printf("%d",ans),0;
for (i=-S;i<=S;++i) if (!pos[i+S].empty())
{
int j=i-k; if (j<-S||j>S) continue;
vector <int> tmp=merge(pos[i+S],pos[j+S]);
int mx=0,cur=0; for (auto x:tmp)
cur=max(cur,0),cur+=x,mx=max(mx,cur);
ans=max(ans,(int)pos[i+S].size()+mx);
}
return printf("%d",ans),0;
}
D. Paimon Sorting
这题ex了徐神一整场，好像有挺多挺难发现的Corner Case的说
徐神早就想写对拍但因为我们的机时严重不足所以就纯靠肉眼观察，最后在结束之前终于是搞出来了
#include <bits/stdc++.h>
using llsi = long long signed int;
#define Tp template <typename T>
#define RI int
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++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
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()));
}
Tp inline void write(T x,const char ch='\n')
{
RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc(ch);
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
#undef Tp
#undef RI
using llsi = long long signed int;
#define lb(i) (i&-i)
int T, n, a[100010], occ[100010], c[100010];
int main() {
std::ios::sync_with_stdio(false);
std::cin >> T; while(T--) {
std::cin >> n;
memset(occ + 1, 0, sizeof(int) * n);
memset(c + 1, 0, sizeof(int) * n);
for(int i = 1; i <= n; ++i) std::cin >> a[i];
llsi ans = 0; occ[a[1]] = 1;
for(int i = a[1]; i <= n; i += lb(i)) c[i] += 1;
std::cout << "0" << char(n == 1 ? 10 : 32);
for(int p = 2; p <= n; ++p) {
if(!occ[a[p]]) {
for(int i = a[p]; i <= n; i += lb(i)) c[i] += 1;
occ[a[p]] = 1;
}
if(a[p] > a[1]) {
ans += 1;
if(occ[a[1]] > 1) ans += p - occ[a[1]] + 1;
else ans += 1;
std::swap(a[1], a[p]);
} else {
for(int i = a[p]; i; i -= lb(i)) ans -= c[i];
for(int i = n; i; i -= lb(i)) ans += c[i];
}
if(occ[a[p]] == 1) occ[a[p]] = p;
if(occ[a[p]] == 0) occ[a[p]] = 1;
std::cout << ans << char(p == n ? 10 : 32);
}
}
return 0;
}
E. Paimon Segment Tree
这场唯一像人的地方就是在中期把这道DS开出来了，但因为代码量还挺大的所以也占了很多机时，也算是间接导致我们罚时起飞了
这题首先很容易想到把版本号看作\(x\)轴，下标看作\(y\)轴，这样询问就是一个矩形求和
那么既然都有矩形求和了就很容易想到用扫描线+差分处理，由于这题的性质，我们很容易对于某个区间\([l,r]\)，维护从初始版本到当前版本的所有版本的平方和，这样询问直接减一下就完事
考虑那我们线段树上需要维护什么信息：所有版本的平方和、当前版本的平方和、当前版本的区间和、当前版本的区间长度
当区间加某个数\(k\)后转移方程是显然的，但现在的问题是我们知道了对于这些信息的修改，但由于涉及到懒标记下传，这里很容易讨论不清楚
而处理的方式也很简单，我们可以直接把上面的四个信息写出向量的形式，然后不难发现加上某个数的转移可以写成矩阵乘法的形式，这样就可以方便维护修改了
最后总复杂度\(O(4^3\times n\log n)\)，需要卡卡常才能过
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
const int N=50005,mod=1e9+7;
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++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
Tp inline void read(T& x)
{
x=0; char ch; int flag=1; while (!isdigit(ch=tc())) if (ch=='-') flag=-1;
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag;
}
Tp inline void write(T x,const char ch='\n')
{
RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc(ch);
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
struct ifo
{
int l,r,x;
}o[N]; int n,m,q,a[N],ans[N]; vector <ifo> ques[N];
inline int sum(CI x,CI y)
{
return x+y>=mod?x+y-mod:x+y;
}
inline int sub(CI x,CI y)
{
return x-y<0?x-y+mod:x-y;
}
struct Matrix
{
int n,m,mat[4][4];
inline Matrix(CI N=4,CI M=4)
{
n=N; m=M; memset(mat,0,sizeof(mat));
}
inline void init(void)
{
memset(mat,0,sizeof(mat)); for (RI i=0;i<4;++i) mat[i][i]=1;
}
inline bool is_init(void)
{
for (RI i=0;i<4;++i) for (RI j=0;j<4;++j)
if (mat[i][j]!=(i==j?1:0)) return 0; return 1;
}
inline int* operator [] (CI x) { return mat[x]; }
friend inline Matrix operator + (Matrix A,Matrix B)
{
Matrix C(A.n,A.m); for (RI i=0,j;i<C.n;++i)
for (j=0;j<C.m;++j) C[i][j]=sum(A[i][j],B[i][j]); return C;
}
friend inline Matrix operator * (Matrix A,Matrix B)
{
Matrix C(A.n,B.m); for (RI i=0,j,k;i<C.n;++i)
for (j=0;j<C.m;++j) for (k=0;k<A.m;++k)
C[i][j]=sum(C[i][j],1LL*A[i][k]*B[k][j]%mod); return C;
}
};
class Segment_Tree
{
private:
Matrix O[N<<2],T[N<<2];
inline void pushup(CI now)
{
O[now]=O[now<<1]+O[now<<1|1];
}
inline void apply(CI now,Matrix it)
{
O[now]=it*O[now]; T[now]=it*T[now];
}
inline void pushdown(CI now)
{
if (!T[now].is_init()) apply(now<<1,T[now]),apply(now<<1|1,T[now]),T[now].init();
}
public:
#define TN CI now=1,CI l=1,CI r=n
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void build(TN)
{
T[now].n=T[now].m=4; T[now].init(); O[now].n=4; O[now].m=1; O[now][3][0]=r-l+1;
if (l==r) return; int mid=l+r>>1; build(LS); build(RS);
}
inline void update(CI beg,CI end,Matrix it,TN)
{
if (beg<=l&&r<=end) return apply(now,it); int mid=l+r>>1; pushdown(now);
if (beg<=mid) update(beg,end,it,LS); if (end>mid) update(beg,end,it,RS); pushup(now);
}
inline void modify(CI beg,CI end,CI x)
{
Matrix tmp(4,4); tmp.init(); tmp[0][1]=1;
tmp[0][2]=tmp[1][2]=2LL*x%mod; tmp[2][3]=x;
tmp[0][3]=tmp[1][3]=1LL*x*x%mod; update(beg,end,tmp);
}
inline Matrix ask(CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return O[now]; int mid=l+r>>1; Matrix ret(4,4); pushdown(now);
if (beg<=mid) ret=ret+ask(beg,end,LS); if (end>mid) ret=ret+ask(beg,end,RS); return ret;
}
inline int query(CI beg,CI end)
{
Matrix tmp=ask(beg,end); return tmp[0][0];
}
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
RI i; for (F.read(n),F.read(m),F.read(q),i=1;i<=n;++i) F.read(a[i]),a[i]=sum(a[i],mod);
for (i=2;i<=m+1;++i) F.read(o[i].l),F.read(o[i].r),F.read(o[i].x),o[i].x=sum(o[i].x,mod);
for (SEG.build(),i=1;i<=q;++i)
{
int l,r,x,y; F.read(l); F.read(r); F.read(x); F.read(y);
ques[y+1].push_back((ifo){l,r,i}); ques[x].push_back((ifo){l,r,-i});
}
for (i=1;i<=n;++i) SEG.modify(i,i,a[i]);
for (auto [l,r,id]:ques[1]) if (id>0) ans[id]=sum(ans[id],SEG.query(l,r));
else ans[-id]=sub(ans[-id],SEG.query(l,r));
for (i=2;i<=m+1;++i)
{
if (o[i].l>1) SEG.modify(1,o[i].l-1,0);
if (o[i].r<n) SEG.modify(o[i].r+1,n,0);
SEG.modify(o[i].l,o[i].r,o[i].x);
for (auto [l,r,id]:ques[i]) if (id>0) ans[id]=sum(ans[id],SEG.query(l,r));
else ans[-id]=sub(ans[-id],SEG.query(l,r));
}
for (i=1;i<=q;++i) F.write(ans[i]);
return F.flush(),0;
}
F. Paimon Polygon
计算几何，但是是防AK题，寄
G. Paimon's Tree
好劲的树上区间DP题，感觉是第一次知道区间DP上树的写法
首先考虑如果我们选定了某条路径\(u\to v\)，钦定最后答案就是上面的边权和
假设上面依次有\(k\)个点，同时顺便求出每个点不在路径上的子树内有多少条边可以用，记为\(b_i\)，不难发现这些边就相当于一个垃圾桶的作用
考虑使用区间DP求解，设\(f_{l,r,t}\)表示已经完成了路径上第\(l\)个点到第\(r\)个点的路径上边的赋值，同时从序列\(a\)中用了\(t\)个数，所得到的最大权值和，则转移有：
- \(f_{l,r,t}\to f_{l-1,r,t+1}+a_{t+1}\)
- \(f_{l,r,t}\to f_{l,r+1,t+1}+a_{t+1}\)
- \(f_{l,r,t}\to f_{l,r,t+1}\)，需要满足\(\sum_{i=l}^r b_i\ge t+1-(r-l)\)
然后我们考虑怎么把这个DP搞到树上去，这里提一嘴在QOJ上看到一个很炸裂的做法
就是直接暴枚路径的两个端点，然后跑上面的区间DP，算了下复杂度极限是\(O(n^5)\)的，不知道是数据水了还是对cache记为友好居然能跑过去
考虑复杂度正确的做法，不难发现上面的暴力做法有很多重复计算的信息没有利用上
考虑上面的DP在树上和在序列上的区别，其实无非就是不能确定端点是否还要向两边扩展，以此带来的能放垃圾的边的数量的区别
因此我们可以给我们的DP多开一维\(0\sim 3\)，状压表示两个端点是否还要扩展，不难发现转移的思路和之前是类似的
然后这题就做完了，总复杂度\(O(n^3)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=155,INF=1e18,ct[4]={0,1,1,2};
int t,n,a[N],x,y,f[N][N][N][4],anc[N][N],sz[N][N]; vector <int> v[N];
inline void DFS(CI rt,CI now,CI fa=0)
{
anc[rt][now]=fa; sz[rt][now]=1;
for (auto to:v[now]) if (to!=fa) DFS(rt,to,now),sz[rt][now]+=sz[rt][to];
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i,j,k,tp; for (scanf("%lld",&n),++n,i=1;i<n;++i) scanf("%lld",&a[i]);
for (i=1;i<=n;++i) v[i].clear();
for (i=1;i<n;++i) scanf("%lld%lld",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (i=1;i<=n;++i) DFS(i,i);
for (i=1;i<=n;++i) for (j=1;j<=n;++j) for (k=0;k<=n;++k) for (tp=0;tp<4;++tp) f[i][j][k][tp]=-INF;
for (i=1;i<=n;++i) f[i][i][0][3]=0;
for (k=0;k<n-1;++k) for (tp=3;tp>=0;--tp) for (i=1;i<=n;++i) for (j=1;j<=n;++j)
{
if (f[i][j][k][tp]==-INF) continue;
int fi=anc[j][i],fj=anc[i][j],w=f[i][j][k][tp],left=i==j?0:n-sz[j][i]-sz[i][j]+ct[tp]-1;
//printf("%lld %lld %lld %lld %lld\n",i,j,k,tp,w);
auto upd=[&](CI i,CI j,CI k,CI tp,CI w)
{
if (w>f[i][j][k][tp]) f[i][j][k][tp]=w;
};
if (tp==3)
{
for (auto si:v[i]) if (si!=fi) upd(si,j,k,1,w);
for (auto sj:v[j]) if (sj!=fj) upd(i,sj,k,2,w);
if (k+1<=left) upd(i,j,k+1,3,w);
}
if (tp==2)
{
for (auto si:v[i]) if (si!=fi) upd(si,j,k,0,w);
upd(i,j,k+1,3,w+a[k+1]);
if (k+1<=left) upd(i,j,k+1,2,w);
}
if (tp==1)
{
for (auto sj:v[j]) if (sj!=fj) upd(i,sj,k,0,w);
upd(i,j,k+1,3,w+a[k+1]);
if (k+1<=left) upd(i,j,k+1,1,w);
}
if (tp==0)
{
upd(i,j,k+1,1,w+a[k+1]); upd(i,j,k+1,2,w+a[k+1]);
if (k+1<=left) upd(i,j,k+1,0,w);
}
}
int ans=0; for (i=1;i<=n;++i) for (j=1;j<=n;++j)
ans=max(ans,f[i][j][n-1][3]); printf("%lld\n",ans);
}
return 0;
}
H. Crystalfly
刚开始想假了随便上去写了个DP发现样例都过不了，但后面发现也不是那么假，随便改了下就过了
首先注意到\(t_i\le 3\)，不难发现当我们到达某个点\(u\)时，设它的儿子节点为\(v\)，不难发现对于\(t_v\ne 3\)的\(v\)我们只能选其中至多一个点抓到蝴蝶
若存在\(t_v=3\)的子节点，我们可以先去\(u\)的另一个儿子节点\(w\)抓蝴蝶，完事后回到\(v\)把\(v\)上的蝴蝶抓了，然后再走回\(w\)的子树抓蝴蝶
考虑令\(f_i\)表示在\(i\)的子树内（不包括\(i\)）中最多能抓到多少蝴蝶，最后的答案就是\(f_1+a_1\)
令\(s_i\)为\(i\)所有儿子的\(f\)之和，则转移为：
- \(f_u=\max (s_u+a_v)\)
- \(f_u=\max_{v\ne w,t_v=3} (s_u-f_w+a_w+s_w+a_v)\)
第二种转移可以枚举\(v\)，不难发现此时只要维护所有儿子节点\(-f_w+a_w+s_w\)的最大值和次大值即可\(O(1)\)转移
总复杂度\(O(n)\)
#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=100005,INF=1e18;
int T,n,x,y,a[N],t[N],f[N],sum[N]; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
f[now]=sum[now]=0; pi mx=pi(-INF,0),smx=pi(-INF,0);
for (auto to:v[now]) if (to!=fa) DFS(to,now),sum[now]+=f[to];
for (auto to:v[now]) if (to!=fa)
{
f[now]=max(f[now],sum[now]+a[to]); pi tmp=pi(sum[to]+a[to]-f[to],to);
if (tmp>mx) smx=mx,mx=tmp; else if (tmp>smx) smx=tmp;
}
for (auto to:v[now]) if (to!=fa&&t[to]==3)
f[now]=max(f[now],sum[now]+a[to]+(to!=mx.second?mx.first:smx.first));
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0);
for (cin>>T;T;--T)
{
RI i; for (cin>>n,i=1;i<=n;++i) v[i].clear(),cin>>a[i];
for (i=1;i<=n;++i) cin>>t[i];
for (i=1;i<n;++i) cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
DFS(); cout<<f[1]+a[1]<<endl;
}
return 0;
}
I. Cloud Retainer's Game
这题貌似不难，最后祁神和徐神讨论也会了这个题，但由于机时的问题没时间给祁神调试了
不知道后面祁神补了没这个题，既然队友会了我就不管了
J. Xingqiu's Joke
唉可惜徐神最后想D题想红温了，然后我下机推J推了半小时发现其实徐神早就想到了，这下纯没作用了
不妨设\(a<b\)，发现除法操作可能除去的质数\(p\)一定满足\(p|(b-a)\)，同时不难发现先加减再做除法比先除再加减来的优
这就提示我们可以以除法操作来划分转移状态，考虑令\(f_{x,y}\)表示将\(a=x,b-a=y\)的状态变成\(a=1\)的状态需要的最少步数
我们枚举所有的\(p|y\)，则\(f_{x,y}\)可以由\(f_{\lfloor\frac{x}{p}\rfloor,\frac{y}{p}},f_{\lceil\frac{x}{p}\rceil,\frac{y}{p}}\)转移过来，代价的话也很容易推出来
由于\(10^9\)范围内一个数的质因子数量不会很多，因此这个东西的有效状态数其实很少，我们可以直接大力DP出来
但刚开始冲的版本用mapTLE飞了，后面灵机一动把两个int数转成一个long long扔进unordered_map然后就直接过了
#include<cstdio>
#include<iostream>
#include<unordered_map>
#include<vector>
#include<utility>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,base=1000000001;
int t,a,b,pri[N],cnt; bool vis[N]; unordered_map <int,int> f;
inline void init(CI n)
{
for (RI i=2,j;i<=n;++i)
{
if (!vis[i]) pri[++cnt]=i;
for (j=1;j<=cnt&&i*pri[j]<=n;++j)
if (vis[i*pri[j]]=1,i%pri[j]==0) break;
}
}
inline int F(int x,int g,vector <int> frac)
{
if (x==1) return 0; if (g==1) return x-1;
int state=x*base+g; if (f.count(state)) return f[state];
int ret=x-1; for (RI i=0;i<frac.size();++i)
{
int p=frac[i]; vector <int> tmp=frac; tmp.erase(tmp.begin()+i);
int y=x/p; if (y) ret=min(ret,F(y,g/p,tmp)+x-y*p+1);
y=(x+p-1)/p; ret=min(ret,F(y,g/p,tmp)+y*p-x+1);
}
return f[state]=ret;
}
signed main()
{
for (scanf("%lld",&t),init(100000);t;--t)
{
scanf("%lld%lld",&a,&b); if (a>b) swap(a,b);
vector <int> frac; int x=b-a;
for (RI i=1;i<=cnt&&1LL*pri[i]*pri[i]<=x;++i)
while (x%pri[i]==0) frac.push_back(pri[i]),x/=pri[i];
if (x>1) frac.push_back(x); sort(frac.begin(),frac.end());
printf("%lld\n",F(a,b-a,frac));
}
return 0;
}
K. Ancient Magic Circle in Teyvat
本场最难的一题，鉴定为寄
L. Secret of Tianqiu Valley
疑似是个构造，但过的人少的可怜
M. Windblume Festival
最唐氏的一集，祁神写完WA了后把思路将给徐神和我听后都感觉很对，然后三个人一起对着这个题红温了
最后猛地发现没特判\(n=1\)的情况，不过只能赖自己明明签到题卡Corner Case是很常见的问题了还不注意
这题的思路其实很简单，当序列中有正有负时（\(0\)可以看做任意一种数），答案就是整个序列的元素的绝对值之和
否则当符号全相同时，则其中绝对值最小的元素贡献变成负的，证明很容易手玩一下就能发现
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
//freopen("M.in", "r", stdin);
int t; scanf("%lld", &t);
while (t--){
int n; scanf("%lld", &n);
vector<int> vec(n);
int mn=1e9+5, ans=0;
bool ok=false;
for (int i=0; i<n; ++i){
scanf("%lld", &vec[i]);
ans+=abs(vec[i]);
mn=min(abs(vec[i]), mn);
}
if (n==1) {
printf("%lld\n",vec[0]);
continue;
}
for (int i=1; i<n; ++i) if (vec[i]*vec[0]<=0) ok=true;
if (!ok) ans-=2*mn;
printf("%lld\n", ans);
}
return 0;
}
Postscript
明天晚上应该还有合肥前的最后一次VP，希望比赛的时候手感能好点吧
- Nanjing Regional Contest Grand 2021nanjing regional contest grand acm-icpc regional contest nanjing regional contest nanjing 2022 regional contest nanjing 2023 yesterday regional contest nanjing inscryption regional contest nanjing regional contest macau 2021 shenyang regional contest 2021 universal contest nanjing stage crystalfly nanjing p9847 2021