看标题可能以为是文化课
但其实并不是……
C. 内积
当然先看了一遍所有题目
发现T3是个有趣的线代题目……才怪
这不就……硬排序模拟么……
然后自己手动证明了一下，做差后因式分解很轻松的可以得出结论
就是 $sort$ 一下完事……
#include
#include
#include
#include<string>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000;
int n,a[WR],b[WR];
int ans;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-48;
ch=getchar();
}
return s*w;
}
signed main(){
freopen("nj.in","r",stdin);
freopen("nj.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
sort(a+1,a+1+n);
sort(b+1,b+1+n);
for(int i=1;i<=n;i++){
ans+=a[i]*b[i];
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
然后看了看T4是个动规
好像还挺阳间的样子？
开始大力推式子，在楼梯口徘徊徘徊……
果断弃疗开A题
A. 电压机制
首先很容易想到，节点的高/低电压就相当于 $0/1$ 染色，除了题目所提到的“被选择的电线”，其他的边的两个端点的颜色应该不同。
听起来是不是特别像二分图？所以可以套用一下判断二分图的DFS……检查是否染色成功。(
接下来考虑一下图上的一些性质——环！
① 如果没有环
那么就非常简单了，由于图是全联通的，所以此时图就是一棵树。那么每一条边都可以作为“被选中的边”。原因是：
选择一条边就相当于把它删去，同时将它的两端点染成相同的颜色。但是由于图是一棵树，删除任意一条边都会将树分成两个连通块，两个连通块分别形成一个新的树。既然是树，从一个点开始，就一定可以将整棵树都染上色。
那么上述情况，答案就是边的数量。
② 如果有偶环
很容易想到不能选择在偶环上的边，否则染色就会失败。
比如下面这个例子：
③ 如果有奇环
可以想到选择的边一定要在奇环中，否则会出现下面这种情况：${1,2,3,4,5}$ 构成一个奇环，但是选择了 $1 \to 6$ 的边，也就相当于从 $1$ 开始对奇环染色……很明显是无法完成的。
推广一下，对于每一个奇环，只要它没有一条边被选中，它就一定会从它的某一个点开始染色，而这样染色的结果就只有失败。
所以所有奇环都必须包含有被选择的边，换句话说，如果我们计算出所有奇环的边集——我们能选择的边就只能是所有奇环的边集的交集！
综上所述，除了情况①，我们要选择的边E要满足以下性质：
1. 设第i个偶环的边集为 $A[i]$ ，则对于每一个 $i$ ， $E \notin A[i]$
2. 设第i个奇环的边集为 $B[i]$ ，则对于每一个 $i$ ， $E \in B[i]$
接下来就是进行一个DFS。
说明一下变量：
1. 整个图的奇环的个数为 $cnt$ 。
2. 对于一条边存储一个 $sum$ 值表示该边在多少个奇环内，则判断该边是否满足“包含在任何一个奇环内”时，只需要判断它的 $sum$ 是否等于 $cnt$ 就可以了。
3. $num[u]$ 表示 $u$ 到 $u$ 的父亲（在DFS树里） 的这一条边包含在多少个奇环里（差分数组）。
从1节点开始DFS，同时进行二分图染色。
假设当时在节点 $u$ ，准备扩展到与 $u$ 相连的节点 $v$ —— 如果 $v$ 没有染色，就将 $v$ 染色，继续从 $v$ 扩展；
如果v已经染过色，那么 $u \to v$ 是一条返祖边，众所周知，$u \to v$ 的返祖边与 $u \to v$ 在DFS树上的路径会围成一个环。
对于围成环的情况，判断当 $u$ 的颜色 和 $v$ 的颜色 相同时，就围成了一个奇环，否则围成了一个偶环。
如果围成了一个奇环，则将环内的所有边的 $sum$ 都+1；如果围成偶环，则将环内的所有边的 $sum$ 都减一，这样的话 $sum$ 就不可能达到 $cnt$ ，也就不可能被选择了。
即使上述算法已经比较优秀了，但是仍然会爆炸，因为枚举环上的边时间复杂度太大了！
所以我们需要用到差分，差分数组最显著的性质就是 前缀和 等于原数组。
当找到环时，如果是奇环，则 $num[u]++$ ，$num[v]--$ ，同时将 $u \to v$ 这条返祖边的 $sum$ 加一；
如果是偶环，则 $num[u]--$ ，$num[v]++$ ，同时将 $u \to v$ 这条返祖边的 $sum$ 减一。
除了在找到环时更改 $num$ ，在回溯时，父亲和儿子之间也存在 $num$ 的转换——假设有点 $u$，$v$ ，在DFS树中 $u$ 是 $v$ 的父亲，则 $num[u]+=num[v]$ ，且 $u \to v$ 这一条树边的 $sum$ 也 $+=num[v]$ 。
当整个 DFS 结束后，枚举所有边，判断它的 $sum$ 是否等于 $cnt$ ，如果是，则 $ans++$ 。
#include
#include
#include<string>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000;
struct Edge{
int pre,to,id;
}edge[WR];
int n,m,ans;
int head[WR],tot;
int num[WR],flag[WR],cnt,sum[WR];
bool vis[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-48;
ch=getchar();
}
return s*w;
}
void add(int u,int v,int id){
edge[++tot].pre=head[u];
edge[tot].to=v;
head[u]=tot;
edge[tot].id=id;
}
void dfs(int u){
for(int i=head[u];i;i=edge[i].pre){
if(!vis[edge[i].id]){
vis[edge[i].id]=true;
int v=edge[i].to;
if(flag[v]!=-1){
if(flag[u]==flag[v]){
cnt++;
sum[edge[i].id]++;
num[u]++,num[v]--;
}else{
sum[edge[i].id]--;
num[v]++,num[u]--;
}
}else{
flag[v]=!flag[u];
dfs(v);
sum[edge[i].id]+=num[v];
num[u]+=num[v];
}
}
}
}
signed main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
add(u,v,i);add(v,u,i);
}
memset(flag,-1,sizeof(flag));
flag[1]=0;
dfs(1);
//printf("%lld\n",cnt);
for(int i=1;i<=m;i++){
if(sum[i]==cnt) ans++;
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
然后看一眼T2像是个暴力贪心
B. 括号密码
先来考虑区间不重叠的情况：
对每个区间，统计区间前缀和，设前缀和最小值为 $w$ ，区间总和为 $a$（ $a$ 必须为偶数，否则无解）
使 $a$ 变为 $0$ ，需要从区间外引进括号，只计算引进 ’)‘ 数量，最后判断如果所有条件区间的 ’)‘ 不够，再从外面进口 ’)’
若$a>0$，则需引进 $\frac{a}{2}$ 个 ’)’ ，使得 $a$ 变为 $0$ ，每次贪心选择最右边的 ’(‘ 修改，$w$ 不改变（将这些进口操作记录到答案）
若$a<0$，需将这里的’)’出口到其它区间，贪心选择最左边的’)’修改，$w$ 会增加 $|a|$（但这些修改不计算入答案，我们只计算引入’(‘数量） 最后加上 $frac{w}{2}$ 次区间内部操作，使得前缀和不存在负数。
再来考虑会出现重叠，但是无嵌套：
不妨设这两个区间分别为 $l_i \to r_i$ 和 $l_j \to r_j$，且 $l_j
有一个很简单的解决方法，可以直接将这两个区间拆成 $l_i \to l_j-1,l_j \to r_i,r_i+1 \to r_j$ 即可。
如果区间有嵌套仍可以按这种方法解决，代码实现细节比较多。
时间复杂度：$O(n)$。
#include
#include
#include<string>
#include
#include
D. 排列
$\color{black}{C}\color{red}{Dsidi}$ 解法：考虑先搞前两个数，再搞后两个数
最后把两段拼起来
用二维树状数组维护一下
#include
#include
#include
#include<string>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=2010;
int n,a[WR],b[WR];
int f[WR][WR],g[WR][WR],dp[WR][WR];
int tree[WR][WR];
int ans;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-48;
ch=getchar();
}
return s*w;
}
int lowbit(int x){
return x&(-x);
}
void modify(int x,int y,int val){
for(int i=x;i<=n;i+=lowbit(i)){
for(int j=y;j<=n;j+=lowbit(j)){
tree[i][j]+=val;
}
}
}
int query(int x,int y){
int res=0;
if(x<=0||y<=0) return 0;
for(int i=x;i;i-=lowbit(i)){
for(int j=y;j;j-=lowbit(j)){
res+=tree[i][j];
}
}
return res;
}
int ask(int stx,int edx,int sty,int edy){
return query(edx,edy)+query(stx-1,sty-1)-query(stx-1,edy)-query(edx,sty-1);
}
void pushup(int k){
for(int i=1;i<=n;i++){
if(g[b[k]][i]==0) continue;
if(a[3]4]) modify(b[k],i,g[b[k]][i]);
else modify(i,b[k],g[b[k]][i]);
}
}
signed main(){
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
n=read();
for(int i=1;i<=4;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
for(int i=2;i<=n;i++){
for(int j=1;j){
if((a[2]-a[1])*(b[i]-b[j])>0) f[b[j]][b[i]]=1;
}
}
for(int i=2;i<=n;i++){
for(int j=1;j){
if((a[4]-a[3])*(b[i]-b[j])>0) g[b[j]][b[i]]=1;
}
}
int p=min(a[1],a[2]),q=max(a[1],a[2]);
pair<int,int> tmp=make_pair(p,q);
for(int i=n-2;i>=1;i--){
pushup(i+1);
for(int j=1;j<=n;j++){
int minval=min(b[i],j),maxval=max(b[i],j);
if(tmp.first==1&&tmp.second==2) dp[j][b[i]]=ask(maxval+1,n,1,n);
if(tmp.first==1&&tmp.second==3) dp[j][b[i]]=ask(minval+1,maxval-1,maxval+1,n);
if(tmp.first==1&&tmp.second==4) dp[j][b[i]]=ask(minval+1,maxval-1,minval+1,maxval-1);
if(tmp.first==2&&tmp.second==3) dp[j][b[i]]=ask(1,minval-1,maxval+1,n);
if(tmp.first==2&&tmp.second==4) dp[j][b[i]]=ask(1,minval-1,minval+1,maxval-1);
if(tmp.first==3&&tmp.second==4) dp[j][b[i]]=ask(1,minval-1,1,minval-1);
dp[j][b[i]]*=f[j][b[i]];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans+=dp[i][j];
}
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
正解不是这个……
这玩意诡异至极
$\color{black}{E}\color{red}{afoo}$ 写了400+行（虽然没有压行
#ifdef DEBUG
#include
#include
#include
#include
#include
#include