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，希望比赛的时候手感能好点吧
标签：tmp,CI,now,XXII,int,Asia,Nanjing,include,define From： https://www.cnblogs.com/cjjsb/p/17850063.html