T1 战神归来
Description
Solution
可以大胆猜测，答案一定是可以取得下界的，下界随便乱算就好了。
考虑如何构造最优。可以想到的是，加入我们把终点坐标>=起点坐标的路径叫做右卡，反之叫做左卡，那么能让答案变小的操作一定是在某个交点处交换了地铁卡，而且最优情况一定是在端点处。可以想到的是，对于一个右卡，如果可以让他变优，肯定是选左端点尽可能靠左的左卡。
需要注意的是，并不一定交换之后直接结束，还可以继续操作。
Code
#include <bits/stdc++.h>
using namespace std;
#define IT multiset<int>::iterator
#define Int register int
#define ll long long
#define MAXN 100005
template <typename T> void read (T &x){char c = getchar ();x = 0;int f = 1;while (c < '0' || c > '9') f = (c == '-' ? -1 : 1),c = getchar ();while (c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar ();x *= f;}
template <typename T,typename ... Args> void read (T &x,Args& ... args){read (x),read (args...);}
template <typename T> void write (T x){if (x < 0) x = -x,putchar ('-');if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> void chkmax (T &a,T b){a = max (a,b);}
template <typename T> void chkmin (T &a,T b){a = min (a,b);}
int T,n,m;
struct node{
int l,r,id;
bool operator < (const node &p)const{
return l != p.l ? l < p.l : r < p.r;
}
};
vector <node> prog;
multiset <node> S[2];
void makeit (node A,node B,int p){//在p点汇合并进行交换，A是右卡，B是左卡
if (A.l ^ p) prog.push_back (node{A.id,p,0});
if (B.r + 1 ^ p) prog.push_back (node {B.id,p,0});
prog.push_back (node{A.id,B.id,1});
}
void Solveit (ll &ans){
if (S[0].empty() || S[1].empty()) return ;
node A = *S[0].begin(),B = *S[1].begin();
if (A.r < B.l) S[0].erase (S[0].begin()),Solveit (ans);
else if (B.r < A.l) S[1].erase (S[1].begin()),Solveit (ans);
else{
S[0].erase (S[0].begin()),S[1].erase (S[1].begin());
int maxl = max (A.l,B.l),minr = min (A.r,B.r);
ans -= minr - maxl + 1 << 1;
if (A.r <= B.r){
if (A.r < B.r) S[1].insert (node{A.r + 1,B.r,B.id});
Solveit (ans),makeit (A,B,A.r + 1);
}
else{
if (B.r < A.r) S[0].insert (node{B.r + 1,A.r,A.id});
makeit (A,B,B.r + 1),Solveit (ans);
}
}
}
int ed[MAXN],s[MAXN],t[MAXN];
signed main(){
freopen( "subway.in", "r", stdin );
freopen( "subway.out", "w", stdout );
read (T);
while (T --> 0){
read (n,m),S[0].clear (),S[1].clear (),prog.clear();
ll ans = 0;
for (Int i = 1;i <= n;++ i){
read (s[i],t[i]),ed[i] = s[i];
if (s[i] < t[i]) ans += t[i] - s[i],S[0].insert (node {s[i],t[i] - 1,i});
else ans += s[i] - t[i],S[1].insert (node {t[i],s[i] - 1,i});
}
Solveit (ans);
write (ans),putchar (' ');
for (auto p : prog) if (!p.id) ed[p.l] = p.r;
for (Int i = 1;i <= n;++ i) if (ed[i] ^ t[i]) prog.push_back (node {i,t[i],0});
write (prog.size()),putchar ('
');
for (Int i = 0;i < prog.size();++ i) write (prog[i].id),putchar (' '),write (prog[i].l),putchar (' '),write (prog[i].r),putchar ('
');
}
return 0;
}
T2 组合数问题
Description
Solution
不难看出，答案就是：
[sum_{i=0}^{n} i! imes i^m imes (-1)^i
]
T3 三角形
Description
(nle 5 imes 10^9)
Solution
根据皮克定理
我们可以得到，当且仅当三角形面积为 (frac{1}{2}) 时合法，然后你通过分析可以得出，当且仅当三角形的 边与 (x,y) 轴平行的外接长方形 两边长度互质 且 有两个端点在顶点上成立，所以我们可以得出：
[ ext{ans}=4sum_{i=1}^{n}sum_{j=1}^{m} (n-i) imes (m-j) imes [gcd(i,j)=1]
]
然后你反演一下再杜教筛一下就好了。
具体分析如下：
