扯淡
运气好，运气好。
Day1
control
[Description]
在n*n的带权棋盘内放n个車，使得任意一个未放置車的位置都能被某个車攻击，求这n个車占据位置权值和的最大值。
[Hint]
[Solution]
分别求出每行最大值的和，和每列最大值的和。
[Code]
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1010;
const int INF = 0x7f;
int Gpos[N]; ll Gmax[N];
int Fpos[N]; ll Fmax[N];
ll a[N][N]; ll ans1=0,ans2=0;
int n;
inline int read()
{
int x=0,t=1; char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') t=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return t*x;
}
int main()
{
freopen("control.in","r",stdin);
freopen("control.out","w",stdout);
n=read();
memset(Gmax,-INF,sizeof(Gmax));
memset(Fmax,-INF,sizeof(Fmax));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
a[i][j]=read();
if(a[i][j]>Gmax[i]) {Gmax[i]=a[i][j],Gpos[i]=j;}
if(a[i][j]>Fmax[j]) {Fmax[j]=a[i][j],Fpos[j]=i;}
}
for(int i=1;i<=n;i++) ans1+=Gmax[i],ans2+=Fmax[i];
if(ans1>ans2){
printf("%lld\n",ans1);
for(int i=1;i<=n;i++) printf("%d %d\n",i,Gpos[i]);
}
else{
printf("%lld\n",ans2);
for(int i=1;i<=n;i++) printf("%d %d\n",Fpos[i],i);
}
return 0;
}
permu
[Description]
给定两个1~N的全排列A,B。有两个指针q和p，一开始q、p都为0，可执行以下三种操作：
1.q+1；2.p+1；3.q+1且p+1（Aq+1≠Bp+1时才可以这么做）。
[Hint]
[Solution]
很容易这题的DP方程
$$f[i][j]=f[i+1][j+1]+1，a[i+1]!=b[j+1]$$
$$f[i][j]=min(f[i+1][j],f[i][j+1])+1，a[i+1]==b[j+1]$$
对于第一种转移，我们可以简单地用队列处理：先将f[n][0~n]存在队列中，然后将f[n][0]出队，将f[n][1~n]++，变成f[n-1][0~n-1]，再往队尾添加f[n-1][n]，对f[i+1][0~n]转移到f[i][0~n]的情况亦然。
但这只是能解决第一种转移，第二种转移需要另作处理。对于f[i+1][0~n]到f[i][0~n]的转移，如果a[i+1]==b[j+1]，f[i+1][j+1]就无法通过第一种转移转移到f[i][j]。对每个i，也存在且仅存在一个j，使得f[i][j]无法进行第一种转移（想一想，为什么？）。
对于第二种转移我们可以这样简化：
因为a[i+1]==b[j+1]，所以a[i+1]!=b[j]，所以f[i][j-1]==f[i+1][j]+1。
所以
有了这个方程，就可以在第一种转移完成后，找到使得a[i+1]==b[j+1]的j，取f[i][j]为队列中其前驱元素的值与其后继元素的值加1的较小值为f[i][j]的值。
[Code]
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000100;
int a[N]; int b[N]; int pos[N];
int q[N<<1]; int n;
inline int read()
{
int x=0,t=1; char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') t=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return t*x;
}
int main()
{
freopen("permu.in","r",stdin);
freopen("permu.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();
for(int i=1;i<=n;i++) pos[b[i]]=i;
for(int i=0;i<=n;i++) q[i]=n-i;
int head=0,tail=n;
for(int i=n;i;i--){
int t=pos[a[i]]; head++;
q[head+t-1]=min(q[head+t-2],q[head+t]+1);
q[++tail]=0;
}
printf("%d",n+q[head]);
return 0;
}
pilgrims
[Description]
一棵n个节点的树，有m个神庙，其他点都是交通要道，每个神庙有一个朝圣者，每个朝圣者都想往离自己最远的任意一个神庙走。要封锁一个点，让尽量多的朝圣者走不到想去的神庙。
[Hint]
[Solution]
仍未解决。。。。顺手贴一发sumix173的标程
[Code]
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define dmp (A[c[x]] + e[x])
#define chet(x, y, z) if (x == Am) a += z, n ^= y; else if (x == Bm) b += z, m ^= y;
#define solve(t) if (a == 1 && Am > 0) { \
if (d == Am) res[z] += t; \
else mark[n] += t; \
} \
else if (!a && b == 1 && Bm > 0) { \
if (d == Bm) res[z] += t; \
else mark[m] += t; \
}
const int inf = (int) 1e9 + 10;
using namespace std;
typedef int arr32[600010];
arr32 A, B, c, t, next, g, e, tot, res, mark;
int n, m, x, y, z, ap, ans;
void link(int x, int y, int t)
{
c[++ap] = y, next[ap] = g[x], g[x] = ap; e[ap] = t;
c[++ap] = x, next[ap] = g[y], g[y] = ap; e[ap] = t;
}
void dfs(int z, int f)
{
A[z] = B[z] = -inf;
if (t[z]) A[z] = 0;
for (int x = g[z]; x; x = next[x])
if (c[x] != f)
if (dfs(c[x], z), dmp > A[z]) B[z] = A[z], A[z] = dmp;
else B[z] = max(B[z], dmp);
}
void dfs(int z, int f, int d)
{
int a = 0, b = 0, n = 0, m = 0;
int Am, Bm;
if (d > A[z]) Am = d, Bm = A[z];
else Am = A[z], Bm = max(B[z], d);
for (int x = g[z]; x; x = next[x])
if (c[x] != f) {
chet(dmp, c[x], 1);
if (A[z] != dmp) dfs(c[x], z, max(d, A[z]) + e[x]);
else dfs(c[x], z, max(d, B[z]) + e[x]);
}
chet(d, 0, 1);
for (int x = g[z]; x; x = next[x])
if (c[x] != f) {
tot[z] += res[c[x]];
chet(dmp, c[x], -1);
solve(res[c[x]]);
chet(dmp, c[x], 1);
}
if (t[z]) solve(1);
}
void calc(int z, int f)
{
tot[z] += mark[z];
if (!t[z]) ans = max(ans, tot[z]);
int h = A[z] != B[z] ? mark[z] : 0;
for (int x = g[z]; x; x = next[x])
if (c[x] != f)
if (dmp == A[z]) mark[c[x]] += h, calc(c[x], z);
else calc(c[x], z);
}
int main()
{
freopen("pilgrims.in", "r", stdin);
freopen("pilgrims.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) scanf("%d", &x), t[x] = 1;
for (int i = 1; i < n; ++i) {
scanf("%d %d %d", &x, &y, &z);
link(x, y, z);
}
dfs(1, 0);
dfs(1, 0, -inf);
calc(1, 0);
printf("%d\n", ans);
for (int i = 1; i <= n; ++i)
if (!t[i] && tot[i] == ans) printf("%d\n", i);
}
Day2
four
[Description]
给定a,b,c,d，问是否存在一个数n，恰好有a个因数模4等于0，恰好有b个因数模4等于1，恰好有c个因数模4等于2，恰好有d个因数模4等于3。
[Hint]
[Solution]
这题需要非常复杂的推导，诸多条件，缺一不可。
先考虑将数n唯一分解，分解出来的质数分为3类：2,4p+1,4p+3。
先不考虑2，得出b与d的关系。对于4p+1类质数，无论其幂次是多少，对4的模值始终是1，设n的因数中，只含有4p+1类质数的数的个数为x。对于4p+3类质数，若其幂次和为奇数，其对4的模值是3，若其幂次和为偶数，其对4的模值是1。设使得4p+3类质数幂次和为奇数的方案数为odd，使得4p+3类质数幂次和为偶数的方案数为even，可以证明odd==even或odd==even-1（归纳法），所以我们可以得出b与d的关系：b与d相等，或b-d=x，即b!=0,b>=d,(b-d)|b,(b-d)|d。
a和c的关系就简单些了，考虑n对2的幂次，若为0，则a=0,c=0；若为1，则a=0,c=b+d(想一想，为什么？)；若大于1，则c|a,c=b+d。
[Code]
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,b,c,d;
inline ll read()
{
ll t=1,x=0; char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') t=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+(ll)ch-'0';
ch=getchar();
}
return t*x;
}
int main()
{
freopen("four.in","r",stdin);
freopen("four.out","w",stdout);
while(1){
a=read(); if(a==-1) break;
b=read(); c=read(); d=read();
if(!b || b<d) {puts("0");continue;}
if(b>d && (b%(b-d) || d%(b-d))) {puts("0");continue;}
if(!c && !a) {puts("1");continue;}
if(!c && a) {puts("0");continue;}
if(c!=b+d) {puts("0");continue;}
if(!a) {puts("1");continue;}
if(a%c) {puts("0");continue;}
puts("1");
}
return 0;
}
sequence
[Description]
给定一个长为n的非负整数数列，求所有不降子序列的元素积的和(mod 10^9+7)。
[Hint]
[Solution]
考虑ans[i]为以i这个数结尾的不降子序列的元素积的和。对于当前数值，不难得出
$$ans[x]=(∑ans[y]+1)*x,(y<=x)$$
离散化后，树状数组即可。
[Code]
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100100;
const int Mod = 1000000007;
struct node{ll x; int id;}data[N];
bool cmp(const node& data1,const node& data2)
{return data1.x<data2.x;}
ll a[N]; ll tr[N]; ll ans[N]; int pos[N];
int n,cnt=0; ll tot=0;
inline ll read()
{
ll t=1,x=0; char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') t=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+(ll)ch-'0';
ch=getchar();
}
return t*x;
}
void Update(int x,ll y)
{
for(int i=x;i<=cnt;i+=(i&-i))
tr[i]=(tr[i]+y+Mod)%Mod;
}
ll Query(int x)
{
ll res=0;
for(int i=x;i;i-=(i&-i))
res=(res+tr[i])%Mod;
return res;
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) data[i].x=a[i];
for(int i=1;i<=n;i++) data[i].id=i;
sort(data+1,data+n+1,cmp);
pos[data[1].id]=++cnt;
for(int i=2;i<=n;i++)
pos[data[i].id]=data[i].x==data[i-1].x?cnt:++cnt;
for(int i=1;i<=n;i++){
ll res=(Query(pos[i])+1)*(a[i]%Mod)%Mod;
Update(pos[i],res-ans[pos[i]]); ans[pos[i]]=res;
}
for(int i=1;i<=cnt;i++) tot=(tot+ans[i])%Mod;
printf("%lld",tot); return 0;
}
plr
[Description]
给定一张n个点m条边的有向图，定义0到n-1号节点的每条路径都要经过的边为“关键边”，用两条长为p的隧道覆盖任意一条0到n-1号节点的路径，使得被覆盖的“关键边”最长。
[Hint]
[Solution]
显然，覆盖要选择在最短路上覆盖。
先求“关键边”，先跑出一条最短路，所有“关键边”必然在这条最短路上。删去最短路上的边并建立其反向边，在新图中求SCC，如果某条最短路上的边的反向边没有被缩掉（其起点终点不在同一SCC），那么这条边就是“关键边”（想一想，为什么？）。
求覆盖就很简单了。覆盖的起点一定是最短路上的某一个点，只要考虑两种情况：一条长为2p的隧道连续覆盖，和两条长为p隧道分开覆盖。
[Code]
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100100;
const int M = 200100;
const int INF = 0x7f;
struct Edge{int u,v,w,nxt;}a[M<<1];
int head[N]; int Dfn[N]; int Low[N];
int Stack[N]; bool InStack[N]; int belong[N];
int pre[N]; int dis[N]; bool vis[N];
int Scc,top,tot,cnt; queue<int> q;
int path[N]; bool mark[M<<1]; int f[N]; bool val[N];
int T,n,m,p;
inline int read()
{
int t=1,x=0; char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') t=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return t*x;
}
void Addedge(int u,int v,int w)
{
a[++m].u=u; a[m].v=v; a[m].w=w;
a[m].nxt=head[u]; head[u]=m;
}
void Spfa()
{
memset(dis,INF,sizeof(dis));
memset(pre,0,sizeof(pre));
dis[0]=0; q.push(0); vis[0]=true;
while(!q.empty()){
int u=q.front(); q.pop(); vis[u]=false;
for(int i=head[u];i;i=a[i].nxt){
int v=a[i].v;
if(dis[u]+a[i].w<dis[v]){
dis[v]=dis[u]+a[i].w; pre[v]=i;
if(!vis[v]) {q.push(v); vis[v]=true;}
}
}
}
}
void Dfs(int u)
{
if(!u) return; Dfs(a[pre[u]].u);
path[++cnt]=a[pre[u]].u; mark[pre[u]]=true;
}
void Tarjan(int u)
{
Dfn[u]=Low[u]=++tot;
Stack[++top]=u; InStack[u]=true;
for(int i=head[u];i;i=a[i].nxt){
if(mark[i]) continue; int v=a[i].v;
if(!Dfn[v]) Tarjan(v),Low[u]=min(Low[u],Low[v]);
else if(InStack[v]) Low[u]=min(Low[u],Dfn[v]);
}
if(Dfn[u]==Low[u]){
int v; Scc++;
do{
v=Stack[top--];
InStack[v]=false;
belong[v]=Scc;
}while(v!=u);
}
}
void Solve()
{
int ans=0;
int now=1,tmp=0;
for(int i=1;i<=cnt;i++){
while(now<cnt && dis[path[now+1]]-dis[path[i]]<=(p<<1)){
if(val[now]) tmp+=dis[path[now+1]]-dis[path[now]];
now++;
}
if(val[now]) ans=max(ans,tmp+(p<<1)-dis[path[now]]+dis[path[i]]);
else ans=max(ans,tmp);
if(val[i]) tmp-=dis[path[i+1]]-dis[path[i]];
}
now=1,tmp=0;
for(int i=1;i<=cnt;i++){
while(now<cnt && dis[path[now+1]]-dis[path[i]]<=p){
if(val[now]) tmp+=dis[path[now+1]]-dis[path[now]];
now++;
}
f[i]=tmp; if(val[now]) f[i]+=p-dis[path[now]]+dis[path[i]];
if(val[i]) tmp-=dis[path[i+1]]-dis[path[i]];
}
now=1,tmp=0;
for(int i=1;i<=cnt;i++){
while(now<=cnt && dis[path[i]]-dis[path[now]]>p){
tmp=max(tmp,f[now]); now++;
}
ans=max(ans,tmp+f[i]);
}
printf("%d\n",ans);
}
int main()
{
freopen("plr.in","r",stdin);
freopen("plr.out","w",stdout);
T=read();
while(T--){
n=read(); m=read(); p=read();
memset(head,0,sizeof(head));
for(int i=1;i<=m;i++){
a[i].u=read(); a[i].v=read(); a[i].w=read();
a[i].nxt=head[a[i].u]; head[a[i].u]=i;
}
Spfa(); if(dis[n-1]==dis[n]){puts("-1"); continue;}
memset(mark,false,sizeof(mark));
cnt=0; Dfs(n-1); path[++cnt]=n-1;
for(int i=1;i<=m;i++) if(mark[i]) Addedge(a[i].v,a[i].u,a[i].w);
memset(Dfn,0,sizeof(Dfn)); tot=0,top=0,Scc=0;
for(int i=0;i<n;i++) if(!Dfn[i]) Tarjan(i);
memset(val,false,sizeof(val));
for(int i=1;i<cnt;i++) if(belong[path[i]]!=belong[path[i+1]]) val[i]=true;
Solve();
}
return 0;
}
