t1 火柴
设计 \(f[i]\) 为 \(i\) 跟火柴最多的长度，\(g[i]\) 为 \(i\) 根火柴应选哪个放在首位。
考虑到前一位的重要性吊打后一位，显然让 \(f[i]\) 尽量大优先，不然就是 \(g[i]\) 取大。考虑记忆化搜索（DP）即可。
#include<bits/stdc++.h>
#define int long long
#define MN 100010
using namespace std;
const int inf=1ll<<60;
int d[10]={0,2,5,5,4,5,6,3,7,6};
int n, m, a[MN], f[MN], g[MN];
void sol(int x) {
if(x<=0||f[x]!=-1) return;
for(int i=1; i<=m; ++i) {
if(x-d[a[i]]<0) continue;
sol(x-d[a[i]]);
if(f[x-d[a[i]]]==inf) continue;
if(f[x-d[a[i]]]+1>f[x]||f[x]==-1)
f[x]=f[x-d[a[i]]]+1, g[x]=a[i];
else if(f[x-d[a[i]]]+1==f[x]&&a[i]>g[x])
g[x]=a[i];
}
if(f[x]==-1) f[x]=inf;
}
void print(int x) {
if(x<=0) return;
cout << g[x];
print(x-d[g[x]]);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=1; i<=m; ++i)
cin >> a[i];
memset(f,-1,sizeof(f));
f[0]=0, sol(n), print(n);
return 0;
}
t2 球赛
显然是 \(a*x+b*y=p\) 并且 \(0\leq x,y\) 并且 \(x+y\leq n\)
那么考虑他们的通解形式。
\(x=x_0+(p/b)k,y=y_0-(p/a)k\)
首先非负是一种限制，给了一个 \(k\) 的上下界。
那么显然要想 \(x+y\) 尽量小，又 \(b\leq a\)，肯定把 \(k\) 取的最边。
那不是拓欧板子？注意到会爆 longlong /fad
\(a,b\) 很小但是其它很大，然后因为尽量小的约束 \(y\) 也是范围很小。
所以我们枚举 \(y\) 去算就行了（（（
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, p, a, b;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> p >> a >> b;
for(int y=0; y<=2e5; ++y)
if((p-b*y)%a==0) {
int x=(p-b*y)/a;
if(x>=0&&x+y<=n) {
cout << x << " " << y << " " << n-x-y;
return 0;
}
}
cout << -1;
return 0;
}
t3 摆渡车
根据题意，设答案为 \(l\)，显然有
\(l\equiv x+[0,y)\pmod {2x+2y}\)
\(l\equiv p+[0,q)\pmod {p+q}\)
注意到 \(p,q\) 小的要命，选择直接枚举+EXCRT。
要龟速乘法 wwww /dk/dk/dk/dk
其实我这个代码是可以少 log 的，因为 exgcd 重复算了一样的。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int mul(int a,int b,int p) {
b=(b%p+abs(p))%p;
int res=0;
for( ; b; b>>=1) {
if(b&1) res=(res+a)%p;
a=(a+a)%p;
}
return res;
}
int exgcd(int a,int b,int &x,int &y) {
if(b==0) {
x=1, y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int t=x; x=y, y=t-a/b*y;
return d;
}
int sol(int x0,int m,int ai,int mi) {
x0%=m, ai%=mi;
int x, y, d=exgcd(m,mi,x,y);
if((ai-x0)%d!=0) return 1ll<<60;
int mt=m/__gcd(mi,m)*mi;
x=mul((ai-x0)/d,x,mt);
x0=(mul(x,m,mt)+x0)%mt;
return (x0%mt+mt)%mt;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int g, x, y, p, q;
cin >> g;
while(g--) {
cin >> x >> y >> p >> q;
int ans=1ll<<60;
for(int i=0; i<y; ++i)
for(int j=0; j<q; ++j) {
ans=min(ans,sol(x+i,2*(x+y),p+j,p+q));
}
if(ans==1ll<<60) cout << "infinity\n";
else cout << ans << endl;
}
return 0;
}
t4 灯与开关
首先来一大波离散化（不知道怎么形容。
我们搞 \([u,v]\) 在离散花的数组里面包含那个区间，是这么算。
r=lower_bound(sp,sp+1+top,u)-sp;
c=upper_bound(sp,sp+1+top,v)-sp-1;
嗯嗯。
看会题目，首先 xor 差分，这样就区间变双点啦。
就变成了一个图，每次把一条边两个端点取反。
这玩意儿 lgj 讲过的说（
首先对于里面其中的很多个连通图，我们选择分别处理。
对于一个图，当且仅当里面 1 的点的个数为偶数时有解。
为什么呢？我们随便拉两个 1 把他们间的路径都用一次，那么这两个 1 变成 0，其它不变，这个奇偶性不会变，如果是一条边被弄了很多次，我们两次操作贡献抵消就行了捏（
之后考虑怎么构造答案，我们这个图的随便一颗搜索树肯定也有解，前提是这个图它有解，对于这棵树，从叶子网上算就很显然了 qwq
#include<bits/stdc++.h>
#define int long long
#define MN 400010
using namespace std;
int n, m, sp[MN], top, vis[MN], d[MN], rs;
int hd[MN], nxt[MN], to[MN], tot, id[MN];
struct dat { int a, b; } p[MN];
bool cmp(dat ix,dat iy) {
return ix.a<=iy.a;
}
void eadd(int u,int v,int i) {
to[++tot]=v;
id[tot]=i;
nxt[tot]=hd[u];
hd[u]=tot;
}
void sol(int x,int fa) {
vis[x]=1;
for(int i=hd[x]; i; i=nxt[i]) {
int y=to[i];
if(vis[y]) continue;
sol(y,fa);
if(p[y].b) p[x].b^=1, rs++, d[i]=1;
}
if(x==fa&&p[x].b) {
cout << -1;
exit(0);
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=1; i<=n; ++i) {
cin >> p[i].a >> p[i].b;
sp[i]=p[i].a;
}
sort(sp+1,sp+1+n);
top=unique(sp+1,sp+1+n)-sp-1;
sort(p+1,p+1+n,cmp);
p[n+1].b=p[n].b^0;
for(int i=n; i>=1; --i) {
p[i].a=lower_bound(sp+1,sp+1+top,p[i].a)-sp;
p[i].b^=p[i-1].b;
}
for(int i=1; i<=m; ++i) {
int u, v, r, c;
cin >> u >> v;
r=lower_bound(sp,sp+1+top,u)-sp;
c=upper_bound(sp,sp+1+top,v)-sp;
if(r!=c) eadd(r,c,i), eadd(c,r,i);
}
for(int i=1; i<=n+1; ++i)
if(vis[i]==0) sol(i,i);
cout << rs << endl;
for(int i=2; i<=tot; ++i)
if(d[i]) cout << id[i] << " ";
return 0;
}