一些TC题目
曾经我尝试过TC从前往后一道一道版刷，然后就被一道Div.1 Hard卡死了。
在一场TC我Div.2 Hard写不过翻车以后，我决定开始刷TC 的Div.2 Hard和Div1.Medium（因为难度差不多）
目标是100道Div.2 Hard和100道Div.1 Medium。
并且我会把一些好题的简要题解发在这里。
TC Div.2 Hard
进度 [10/100]
SRM 730 2H
题意：给定一棵有根树，标号0~n-1，以0为根，i的父亲<i。 当然给的是父亲数组 每个点有个权值\(w_i\)，满足非严格递增。 现在你可以做两个操作： 1. 给一个点打标记，条件：它不存在任意儿子结点没有标记 2. 删除一个点的标记
最终目标是给0打标记。求一个最小的W，使得存在一种方案，满足任何时刻有标记的点权值和\(\le W\)。
题解：在最优的方案下，过程一定是这样（假设我们要给r标记）： 按照一定顺序，将r的每个子结点标记; 给r打标记; 删除每个子节点的标记;
我们计算的答案就是（设标记r结点（其它不用）的答案为\(ans_r\)）： \(ans_r=\min(\sum_{i=1}^{t-1} w_{s_i}+ans_{s_t},\sum w_{s_i}+w_r)\) 其中\(s_i\)表示r标记子结点的顺序中第i个结点。
是的，这是一个贪心好题。 是的，w递增一点用都没有。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
using namespace std;
int chkmax(int &a,int b){return a<b?a=b,1:0;}
vector<int> w,son[1024];
int wu[1024];
int cmp(int u,int v){
return w[u]+wu[v]<w[v]+wu[u];
}
class StonesOnATreeDiv2 {
private:
#define all(a) a.begin(),a.end()
int mins(int r){
for(vector<int> ::iterator i=son[r].begin();i!=son[r].end();++i){
wu[*i]=mins(*i);
}
sort(all(son[r]),cmp);
int cnt=0,ans=0;
for(vector<int> ::iterator i=son[r].begin();i!=son[r].end();++i){
chkmax(ans,wu[*i]+cnt);
cnt+=w[*i];
}
chkmax(ans,w[r]+cnt);
// printf("%d is %d\n",r,ans);
return ans;
}
public:
int minStones(vector<int> p, vector<int> W) {
int n=p.size();
for(int i=0;i<=n;++i)son[i].erase(all(son[i]));
for(int i=1;i<=n;++i)son[p[i-1]].push_back(i);
w=W;
return mins(0);
}
};你有一个有向图，每个点有恰好一条出边。
现在可以进行一种操作：选择三个点a,b,c，接着将a的编号改为b，b 的编号改为c，c的编号改为b（当然也可以反过来）
你需要计算在进行任意多次操作后，可以得到几个不同的图。
两个图不同当且仅当存在至少一个数i，两个图中点i的出边不同。
点数\(n\le 10\)
编号当然从0到n-1
首先有个思路：我们可以用这种交换法生成一个0到n-1的排列，排列的第i个就是i点得到的新编号，然后就可以得到新图。
但是直接生成排列也是很慢的，我们可以找一找规律并且猜一猜结论（或者可以证明一下）。
打了打表，可以猜到生成的序列逆序对都是偶数。
然后这个其实我可以证明：这种三元旋转操作相当于swap(a,b),swap(b,c)，一次旋转恰好让逆序对个数奇偶性取反，两次就不变了。因为初始序列逆序对个数为0，所以就全是偶数。
是不是所有逆序对个数是偶数的都能生成呢？通过输出个数+DP计算逆序对个数是偶数的排列个数可以发现， 至少在\(n\le 10\)的时候都可以。（具体怎么证明我就不会了）
然后就是：首先用next_permutation生成全排列，然后判断逆序对个数奇偶性，然后生成图，然后hash一下去重，AC了。（我会说unordered_map也可以吗）
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#include <tr1/unordered_set>
using namespace std;
class TrisomorphismEasy {
public:
int a[15],ft[15];
tr1::unordered_set<long long> se;
long long jmcnt[24333333];
int count(long long tos){
int fa=tos%19260817;
while(~jmcnt[fa]){
if(jmcnt[fa]==tos)return 1;
++fa;
}
return 0;
}
void insert(long long tos){
int fa=tos%19260817;
while(~jmcnt[fa]){
++fa;
}
jmcnt[fa]=tos;
}
int count(vector<int> edgeTo) {
memset(jmcnt,-1,sizeof(jmcnt));
int n=edgeTo.size();
for(int i=0;i<n;++i)a[i]=i;
int t,cnt=-1;
do{
t=1;
for(int i=0;i<n;++i)for(int j=i+1;j<n;++j)t^=a[i]>a[j];
if(t){
for(int i=0;i<n;++i)ft[a[i]]=a[edgeTo[i]];
long long tos=0;
for(int i=0;i<n;++i){
tos=tos*n+ft[i];
}
if(!count(tos)){
insert(tos);
++cnt;
}
}
}while(next_permutation(a,a+n));
return cnt;
}
};
SRM 727 2H
给定三个字符串S,A,B，问最少在S里加多少个字符可以使得A是S的子串且B不是。
设\(f_{i,j,k}\) 表示在匹配到S串的第i个字母，并且还没匹配\(S_i\)，A串匹配了j个字母，B串匹配了k个，最少需要加多少个字母。
\(g_{i,j,k}\) 表示在匹配到S串的第i个字母，并且已经匹配了这个字母，A串匹配了j个字母，B串匹配了k个，最少需要加多少个字母。
可以从前往后DP（枚举前面的计算对后面的影响）。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
using namespace std;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
class ManageSubsequences {
public:
int aft[303][303][303],bef[303][303][303];
int minAdded(string S, string A, string B) {
memset(bef,0x3f,sizeof(bef));
memset(aft,0x3f,sizeof(aft));
bef[0][0][0]=0;
int ls=S.length(),la=A.length(),lb=B.length();
S=S+'#';
A=A+' ';
B=B+' ';
for(int i=0;i<=ls;++i){
for(int j=0;j<=la;++j)for(int k=0;k<lb;++k){
chkmin(aft[i][j+(A[j]==S[i])][k+(B[k]==S[i])],bef[i][j][k]);
chkmin(bef[i][j+1][k+(A[j]==B[k])],bef[i][j][k]+1);
chkmin(bef[i+1][j][k],aft[i][j][k]);
}
}
int ans=0x3f3f3f3f;
for(int i=0;i<lb;++i)chkmin(ans,bef[ls][la][i]);
return ans==0x3f3f3f3f?-1:ans;
}
};
SRM 726 2H
有n件事，第i件事要在\([S_i,T_i]\)时间内完成。每个单位时间只能做一件事。
问有多少种完成事情的组合。
就是问有多少种方案选出一些事情使得它们都能被完成。
似乎是状压DP？
但是直接DP会算重啊。
有一个神奇的做法：贪心 的思想，按照\(T_i-S_i\)双关键字升序排序。
然后DP的时候，首先枚举事情，然后枚举原来选择的状态。然后转移的时候，找到位置最靠前的可以选择的位置，只选择这个位置转移。
似乎是最优的，蜜汁AC。
class HeroicScheduled2 {
public:
long long f[2][65536];
long long getcount(vector<int> start, vector<int> finish) {
int n=start.size(),m=1<<16;
f[0][0]=1;
vector<int> s;
for(int i=0;i<n;++i){
s.push_back(start[i]|(finish[i]<<4));
}
sort(s.begin(),s.end());
for(int i=0;i<n;++i){
copy(f[i&1],f[i&1]+m,f[(i&1)^1]);
int l=s[i]&15,r=s[i]>>4;
for(int j=0;j<m;++j){
for(int k=l;k<=r;++k)if(!((j>>k)&1)){
f[(i&1)^1][j|(1<<k)]+=f[i&1][j];
break;
}
}
}
long long ans=0;
for(int i=0;i<m;++i)ans+=f[n&1][i];
return ans;
}
};SRM 725 2H
对于一个每个点有点权的有向森林（每个点入度最多为1但出度没有限制），定义一个点的“聚合权值”为这个点能到达的所有点的点权之和。
给定每个点的点权和“聚合权值”，问是否存在一棵点权为给定点权的有向森林，聚合权值也为给定聚合权值。
\(n\le 14\)
首先，显然每条边都要从聚合权值大的连向小的。
所以先按聚合权值从小到大排个序(从大到小也可以)，这棵树就可以用。
方法1：爆搜+剪枝。
枚举每个点有没有父亲，父亲是谁。
剪枝1：判断到某一个点时如果聚合权值没达到就退出。
剪枝2：搜的时候要求父亲的聚合权值加上孩子的聚合权值不大于要求的聚合权值。
剪枝3：搜到当前点的时候，如果存在一个点聚合权值没达到，并且当前点的父亲也不可能为它否则它聚合权值会超过(此时后面的也会)就退出。
可以A了。
class HiddenTreeDiv2 {
public:
int want[1926],have[1926],n;
int dfs(int x){
if(x>n)return 1;
if(want[x]>have[x])return 0;
int tmx=0x3f3f3f3f;
for(int i=x+1;i<=n;++i){
if(want[i]>have[i])chkmax(tmx,want[i]-have[i]);
}
if(tmx<want[x])return 0;
if(dfs(x+1))return 1;
for(int i=x+1;i<=n;++i)if(have[i]+have[x]<=want[i]){
have[i]+=have[x];
if(dfs(x+1))return 1;
have[i]-=have[x];
}
return 0;
}
string isPossible(vector<int> a, vector<int> b) {
n=a.size();
for(int i=0;i<n;++i)if(a[i]>b[i])return "Impossible";
for(int i=0;i<n;++i)for(int j=i+1;j<n;++j)if(b[i]>b[j]){swap(b[i],b[j]);swap(a[i],a[j]);}
for(int i=0;i<n;++i)want[i+1]=b[i],have[i+1]=a[i];
return dfs(1)?"Possible":"Impossible";
}
};方法2：状压DP。
定义\(f_{i,j}\)表示当前到第i个点，有父亲点的集合为j且前面点的聚合权值全部满足是否可行。
转移的时候枚举一个没有父亲点集合的子集，具体方法参考725 1M。
时间复杂度\(O(n3^n)\)
SRM 724 2H
n个队伍在打循环赛。比赛没有平局。
现在已经知道一些比赛的结果了。
你需要填写其它比赛的结果使得所有队伍胜率的方差尽量大。
显然胜率就是胜的比赛数/打的比赛数。
\(n\le 20\)
显然不能直接贪心（每次找到比赛胜率最低的让它其它每场都输这不是最优策略）。
但是似乎可以给每个队伍一个两两不同的能力值，要求剩下比赛能力值高的队伍必胜。应该是最优秀的。
这个枚举可以优化成状压DP。
显然胜率平均值为0.5。
\(f_i\)表示已经确定i集合的队伍的能力值大于其它队伍的能力值，i集合中每个元素(胜率-0.5)^2的最大值。
只要\(O(n2^n)\)
class UnfinishedTournamentEasy {
public:
int win[66][66],s[66],wsm[66],orz[66][66];
double f[1<<20];
double maximal(vector<string> G) {
int n=G.size();
double moh=0.5;
for(int i=0;i<n;++i)for(int j=0;j<n;++j)if(G[i][j]=='W'){win[i][j]=1;++wsm[i];}else if(G[i][j]=='?')orz[i][j]=1;
int m=1<<n;
for(int i=1;i<m;++i){
for(int j=0;j<n;++j)if(i&(1<<j)){
double th=f[i^(1<<j)];
int fake=wsm[j];
for(int k=0;k<n;++k)if(orz[j][k]&&!(i&(1<<k))){
++fake;
}
double czy=fake*1./(n-1);
th+=(czy-moh)*(czy-moh);
chkmax(f[i],th);
}
}
return f[m-1]/n;
}
};
SRM 723 2H
一个地图形如
A
BCD
E
其中每个字母都表示一个n*n的区域，显然A与CE都对齐。
一共有\(5n^2\)个点。
求点两两之间曼哈顿距离之和\(\mod (10^9+7)\)
\(n\le 10^{18}\)
考虑在单个区域内的答案：
对于行答案为\(n^2\sum_{i=1}^{n}\sum_{j=i}^{n}|i-j|=n^2\sum_{i=1}^{n}\sum_{j=1}^{n-i}j\)
这个\(n^2\)外的东西显然可以矩阵快速幂和求解。
记它为\(Sa\)。
单个区域内答案就是\(2Sa\)。
考虑AC两个区域内的答案。
列间距离和是2Sa
行间距离和为\(n^2\sum_{i=1}^n\sum_{j=1}^n(j+n-i)=n^5\)
记为\(Sb\)
经过计算发现答案就是\(22Sa+16Sb\)
const ll p=1000000007;
struct matrix{
ll a[3][3];
ll *operator[](ll b){return a[b];}
matrix operator +(matrix b){
matrix c;
for(ll i=0;i<3;++i)for(ll j=0;j<3;++j)c[i][j]=(a[i][j]+b[i][j])%p;
return c;
}
matrix operator *(matrix b){
matrix c;
for(ll i=0;i<3;++i)for(ll j=0;j<3;++j){
c[i][j]=0;
for(ll k=0;k<3;++k)
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%p;
}
return c;
}
matrix operator ^(ll b){
matrix a=*this,c;
for(ll i=0;i<3;++i)for(ll j=0;j<3;++j)c[i][j]=i==j;
while(b){
if(b&1)c=c*a;
a=a*a;
}
return c;
}
};
matrix a,b,c;
void qsum(long long n){
if(n==1){
for(ll i=0;i<3;++i)for(ll j=0;j<3;++j)c[i][j]=(i==j);
b=a;
return ;
}
if(n&1){
qsum(n-1);
c=c+b;
b=b*a;
}
else{
qsum(n>>1);
c=c+c*b;
b=b*b;
}
}
class SimpleMazeEasy {
public:
ll findSum(long long n) {
if(n==1){
return 16;
}
for(ll i=0;i<3;++i)for(ll j=0;j<3;++j)a[i][j]=(i<=j);
qsum(n-1);
for(ll i=0;i<3;++i)for(ll j=0;j<3;++j)b[i][j]=!j;
a=c*b;
n%=p;
ll s1=a[0][0],s2=n;
// printf("%lld\n",s1);
s2=(long long)s2*s2%p;
s1=s1*s2%p;
s2=(long long)s2*s2%p;
s2=s2*n%p;
// printf("%lld %lld\n",s1,s2);
return (long long)(s1*22+s2*16)%p;
}
};SRM 722 2H
见1M，2H是1M的Easy。
SRM 721 2H & 1H
给定一棵树，有一些点有令牌，同时这些点也有炸弹。有t秒，每秒可以按顺序把一些令牌移动一个位置。最后要求每个令牌位置互不相同。然后炸弹会爆炸，同点的令牌就会坏掉。问最多几个令牌不坏。
对于2H，途中不要求令牌位置互不相同。
对于1H，任何时候令牌位置互不相同。
网络流。
建源点建汇点。
对于2H：
每个令牌建个点，有炸弹的源点连向它一条边，没有的连汇点一条边。
对所有有炸弹的点，向所有没有炸弹的距离t以内的点连边。
（边权1）
然后最大流。
class ApocalypseEasy {
public:
int to[192608],lst[192608],beg[128],w[192608],e,cur[128],n;
void add(int u,int v,int wa){
// if(wa)printf("%d->%d(%d)\n",u,v,wa);
to[++e]=v;
lst[e]=beg[u];
beg[u]=e;
w[e]=wa;
}
vector<int> graph[128];
int ok[128],vis[128];
void dfs(int x,int t){
if(vis[x])return;
vis[x]=1;
if(!t)return ;
for(auto i:graph[x])dfs(i,t-1);
}
int dis[128];
int q[128],*l,*r;
int bfs(int s,int t,int n){
for(int i=0;i<n;++i)cur[i]=beg[i];
for(int i=0;i<n;++i){dis[i]=0x3f3f3f3f;}
*(l=r=q)=s;
dis[s]=0;
while(l<=r){
for(int i=beg[*l];i;i=lst[i])if(w[i]&&dis[to[i]]==0x3f3f3f3f){
dis[to[i]]=dis[*l]+1;
*(++r)=to[i];
}
++l;
}
return dis[t]!=0x3f3f3f3f;
}
int dfs(int s,int t,int flow){
if(!flow)return 0;
// debug("hh??%d,%d,%d\n",s,t,flow);
if(s==t)return flow;
for(;cur[s];cur[s]=lst[cur[s]])if(w[cur[s]]){
int i=cur[s];
if(dis[s]+1==dis[to[i]]){
int g=dfs(to[i],t,min(flow,w[i]));
if(g){
w[i]-=g;
w[i^1]+=g;
return g;
}
}
}
return 0;
}
int dinic(int s,int t,int n){
int ans=0,flow;
while(bfs(s,t,n)){
while(flow=dfs(s,t,0x3f3f3f3f))ans+=flow;
}
return ans;
}
int maximalSurvival(vector<int> p, vector<int> position, int t) {
++e;
int n=p.size(),m=position.size();
for(int i=0;i<n;++i)graph[i+1].push_back(p[i]),graph[p[i]].push_back(i+1);
++n;
for(int i=0;i<n;++i)ok[i]=1;
for(int i=0;i<m;++i){
ok[position[i]]=0;
}
for(int i=0;i<n;++i)if(!ok[i]){
add(n,i,1);add(i,n,0);
}else{
add(i,n+1,1);add(n+1,i,0);
}
for(int i=0;i<m;++i){
for(int j=0;j<n;++j)vis[j]=0;
dfs(position[i],t);
for(int j=0;j<n;++j)if(vis[j]&&ok[j]){
add(position[i],j,1);
add(j,position[i],0);
}
}
return dinic(n,n+1,n+2);
}
};
1H：
由于有限制，我们需要对每秒建点，并且每个点每秒要两个点。一个入一个出。入连向出一条边。
s连向所有有炸弹的点的表示0s入点的点。没炸弹的点对应的t秒出点向t连条边。
对于每条树边\(u,v\)，对于\(0\le i<t\),u i秒的出点连向v i+1秒的入点，v连u也一样。
然后每个点u 对于\(0\le i<t\) ,u i秒的出点连向i+1秒的入点。
跑最大流。
class Apocalypse {
public:
int to[192608],lst[192608],w[192608],beg[6666],e,safe[1926];
void add(int u,int v,int wa){
u<<=1;v<<=1;
if(wa&&u!=v||!wa&&u==v)++u;
else ++v;
to[++e]=v;
lst[e]=beg[u];
beg[u]=e;
w[e]=wa;
}
int cur[6666],dis[6666];
int q[6666],*l,*r;
int bfs(int s,int t,int n){
for(int i=0;i<n;++i)cur[i]=beg[i],dis[i]=0x3f3f3f3f;
dis[s]=0;
*(l=r=q)=s;
while(l<=r){
for(int i=beg[*l];i;i=lst[i])if(w[i]&&chkmin(dis[to[i]],dis[*l]+1))*(++r)=to[i];
++l;
}
return dis[t]!=0x3f3f3f3f;
}
#define cs cur[s]
int dfs(int s,int t,int flow){
if(s==t)return flow;
if(!flow)return 0;
for(;cs;cs=lst[cs])if(w[cs]&&dis[s]+1==dis[to[cs]]){
int wr=dfs(to[cs],t,min(flow,w[cs]));
if(wr){
w[cs]-=wr;
w[cs^1]+=wr;
return wr;
}
}
return 0;
}
int dinic(int s,int t,int n){
int ans=0,flow;
while(bfs(s,t,n)){
while(flow=dfs(s,t,0x3f3f3f3f))ans+=flow;
}
return ans;
}
int maximalSurvival(vector<int> p, vector<int> position, int t) {
e=1;
int n=p.size()+1,m=n-1;
for(int T=0;T<t;++T){
for(int i=0;i<m;++i){
add((T*n+i+1),(T+1)*n+p[i],1);
add((T+1)*n+p[i],T*n+i+1,0);
add(T*n+p[i],(T+1)*n+i+1,1);
add((T+1)*n+i+1,T*n+p[i],0);
}
for(int i=0;i<n;++i){
add(T*n+i,(T+1)*n+i,1);
add((T+1)*n+i,T*n+i,0);
}
}
for(int i=0;i<n;++i)safe[i]=1;
for(auto i:position)safe[i]=0;
int u=(t+1)*n;
for(int i=0;i<u;++i){
add(i,i,1);
add(i,i,0);
}
for(int i=0;i<n;++i)if(safe[i]){
add(i+t*n,u,1);
add(u,i+t*n,0);
}
else{
add(u,i,1);
add(i,u,0);
}
return dinic(u*2+1,u*2,(u+1)*2);
}
};
TC Div.1 Medium
进度 [10/100]
SRM 730 1M
给定k，要求构造一个图，使得：
- 点数在1和2k之间
- 标号从0开始
- 是个无向简单图
- 对于任意\(0\le x \le \frac{k(k-1)}{2}\)，存在一个子图，使得有k的点，x条边。
这里子图的定义是说，一些点和所有两端都在这些点中的边的集合。
输出是这样的：
首先给出邻接矩阵，接着对于任意x，从小到大输出这个x对应的选择点方案。
Topcoder哪里需要输出？
只需要返回有这些构成的vector
条件3 的\(\frac{k(k-1)}{2}\)
就是说明，甚至需要有完全子图。
一个非常迷的构造。 把点分为AB两组，各k个点，标号从0到k-1。
A组是个完全图，B组里面没有边。
当\(0\le i \le j <k\)时，存在一个从\(B_i\)点到\(A_j\)点的边。
我们考虑A组里面有i个点，其中i从0到k-1。
则B组里面有(n-i)个点。
初始化令A组里面的点用\(A_0\)\(A_{i-1}\)，B组里面的点用\(B_i\)\(B_{k-1}\)，则此时的答案就是\(\frac{i(i-1)}{2}\)。 接着，每次不选择B中选择了的编号最小的点，然后选择比它编号小一个的点，直到选的点编号为0就不选并退出。每次选完以后，就得到了新的选择序列，并且答案会+1 这样随着最小的点的标号从i到1,边数就从\(\frac{i(i-1)}{2}\)到\(\frac{i(i+1)}{2}-1\),就这样无缝链接。
就做完了
事实上我们还需要输出边数为\(\frac{k(k-1)}{2}\)的子图。
那就是a啊。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
using namespace std;
class Subgraphs {
public:
char graph[1926][1926];
char ths[1926];
vector<string> findGroups(int k) {
vector<string> vs;
for(int i=0;i<k+k;++i){
for(int j=0;j<k+k;++j)graph[i][j]='0';
graph[i][k+k]=0;
}
for(int i=0;i<k;++i){
for(int j=0;j<i;++j)graph[i][j]=graph[j][i]='1';
for(int j=0;j<=i;++j)graph[i][j+k]=graph[j+k][i]='1';
}
for(int i=0;i<k+k;++i){
vs.push_back(graph[i]);
ths[i]=i<k?'N':'Y';
}
int n=k+k;
ths[n]=0;
for(int i=0;i<k-1;++i){
ths[i]='Y';
ths[i+k]='N';
vs.push_back(ths);
for(int j=k+i+1;j>k+1;--j){
ths[j]='N';
ths[j-1]='Y';
vs.push_back(ths);
}
ths[k+1]='N';
ths[n]=0;
}
ths[k-1]='Y';
ths[n-1]='N';
vs.push_back(ths);
return vs;
}
};SRM 729 1M
在一个n*n的棋盘上有一只蛤紫阳站在s的位置上，它要去t的位置。
这只蛤只能站在整点位置，且不能跳出棋盘。
蛤每一步跳跃必须至少跳d的距离。
也就是说欧几里得距离至少为d，问最少跳几步能跳到t。
\(n\le 1000\)
可以猜到（我也不知道怎么猜到的），有一种最优解，除了最后一步外，蛤每一步都会跳到边界上。
然后就可以把起点终点和所有边界上的整点取出来bfs。
注意特判起点终点重合的情况。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
using namespace std;
class FrogSquare {
public:
#define sqr(x) ((x)*(x))
int dx[8888],dy[8888],t;
int dis[8888],q[8888],*l,*r;
int minimalJumps(int n, int d, int sx, int sy, int tx, int ty) {
t=0;
d*=d;
dx[++t]=sx;
dy[t]=sy;
dx[++t]=tx;
dy[t]=ty;
if(sx==tx&&sy==ty)return 0;
for(int i=0;i<n;++i){
dx[++t]=i;
dy[t]=0;
dx[++t]=i;
dy[t]=n-1;
dx[++t]=0;
dy[t]=i;
dx[++t]=n-1;
dy[t]=i;
}
*(l=r=q)=1;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
while(l<=r){
for(int i=1;i<=t;++i)if(dis[i]==0x3f3f3f3f&&sqr(dx[i]-dx[*l])+sqr(dy[i]-dy[*l])>=d){
dis[*(++r)=i]=dis[*l]+1;
}
++l;
}
return dis[2]==0x3f3f3f3f?-1:dis[2];
}
};SRM 728 1M
给定两个下标0到n-1的序列L,R，求有多少个严格递增的数列\(A_0,\dots A_{n-1}\)，使得$ L_iA_i R_i$
\(n\le 300\)，在\(2M\)里面\(L_i\le R_i\le 10^4\)，在\(1M\)里面\(L_i\le R_i\le 10^9\)
对于2M可以很显然的DP，但是1M不能直接用类似的方法。 （我会说先看完2M以后看1M时想了很久离散化套2M的方法吗直到找到tourist的题解吗？） （没错这套题是tourist出的）
大概的做法就是，首先把\(R_i+1\)，这样\(A_i\)的区间就是左闭右开。
接着离散化，得到很多左闭右开区间，每个\(A_i\)的区间就是连续的几个区间，记为区间\(l_i\dots r_i\)。
我们发现，一个长度为b的严格上升子序列整个在一个长度为a区间内的方案数为\(\binom{a}{b}\)
记\(f(n,m)\)表示前n个数在前m个区间的方案数。\(g(n,m)\)表示前n个数在前m个区间且第n个数在第m个区间的方案数。
显而易见f的第2维是g的前缀和。
\(g(n,m)=\sum_i \binom{siz_m}{n-i+1}f(i-1,m-1)\) 其中\(siz_m\)表示第m个区间的大小，i满足\(i\le n\)并且对于任意\(i\le j\le n\)l_jm r_j$
组合数可以利用\(\binom{n}{m}=\frac{n-m+1}{m}\binom{n}{m-1}\) 快速计算。
时间复杂度\(O(n^3)\)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
class IncreasingSequences {
public:
ll f[333][633],inv[333];
vector<int> lsh;
const ll p=998244353;
int count(vector<int> L, vector<int> R) {
ll n=L.size();
L.insert(L.begin(),0);
R.insert(R.begin(),0);
inv[1]=1;
for(ll i=2;i<=n;++i){
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(ll i=1;i<=n;++i)lsh.push_back(L[i]),lsh.push_back(R[i]+1);
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
ll m=lsh.size()-1;
lsh.insert(lsh.begin(),0);
for(ll i=1;i<=n;++i){
L[i]=lower_bound(lsh.begin()+1,lsh.end(),L[i])-lsh.begin();
R[i]=upper_bound(lsh.begin()+1,lsh.end(),R[i])-lsh.begin()-1;
}
f[0][0]=1;
for(ll i=1;i<=m;++i)f[0][i]=1;
for(ll i=1;i<=n;++i){
for(ll j=L[i];j<=R[i];++j){
f[i][j]=f[i][j-1];
ll s=1;
for(ll k=i;L[k]<=j&&j<=R[k];--k){
s=s*(lsh[j+1]-lsh[j]-(i-k))%p*inv[i-k+1]%p;
f[i][j]=(f[i][j]+s*f[k-1][j-1])%p;
}
}
for(ll j=R[i]+1;j<=m;++j)f[i][j]=f[i][j-1];
}
return (int)f[n][m];
}
};SRM 727 1M
有一个矩形网格，其中有一个矩形是标记为#的，其它的标记为.
把这个矩形网络上的标记从上到下，从左到右输出，就能得到一个序列。
现在这个序列被某个小学生胡浩弄丢了几个字符，问想要还原出一种可能的满足条件的矩形网络最少加上几个字符？
首先枚举网络的列数\(M\)，然后枚举标记矩形的列数\(m\)。
可以发现在原来第一个#和最后一个#之间一定是m个#和\(n-m\)个.交替，如果不够了就加上。
注意m个#不能被分到两行。所以如果被分到了两行就在开始加.
最后，如果不满行就用.填满。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
using namespace std;
class Subrectangle {
public:
int minMissed(string S) {
int n=S.length(),lx=n,rx=-1,cnt=0;
for(int i=0;i<n;++i)if(S[i]=='#'){
if(lx==n)lx=i;
rx=i;
++cnt;
}
if(lx==n)return 1;
if(rx-lx+1==cnt)return 0;
int minx=0x3f3f3f3f,t=0,py=0,z0,z1;
for(int K=2;K<=n;++K)for(int k=1;k<K;++k){
py=lx;
t=0;
if(lx/K!=(lx+k-1)/K){
py+=(t+=(K-lx%K));
}
z0=0;z1=k;
for(int i=lx;i<=rx;++i){
if(z1){
if(S[i]=='#'){--z1;++py;}
else{
py+=z1;
t+=z1;
z1=0;
--i;
}
if(!z1)z0=K-k;
}
else{
if(S[i]=='.'){--z0;++py;}
else{
py+=z0;
t+=z0;
z0=0;
--i;
}
if(!z0)z1=k;
}
}
if(z1){
t+=z1;
py+=z1;
}
py+=n-rx-1;
if(py%K)t+=K-(py%K);
minx=min(minx,t);
}
return minx;
}
};
SRM 726 1M
有一棵n个点的树（标号\(0\dots n-1\)。
你需要选择一个\(0\dots n-1\)的排列，然后按照排列顺序访问每个点。
具体就是：首先到达排列第一个点，然后在树上走到第2个点，一直到第n个。然后离开。
要求总共走过的点数最多。
求出这个排列。
枚举起点然后每次BFS找没选过的最远点。
然后取最优解。
就过了？？？
SRM 725 1M
对于一个每个点有点权的有向森林（每个点入度最多为1但出度没有限制），定义一个点的“聚合权值”为这个点能到达的所有点的点权之和。
对于一组聚合权值，一个有向森林是好的，当且仅当存在一组正整数权值使得这棵树的聚合权值恰好为给定的聚合权值。
给定一组聚合权值，问有多少个有向森林是好的（mod 998244353)
显然一个有向森林是好的，当且仅当每个点的所有出边的聚合权值之和严格小于它的聚合权值。
按聚合权值从小到大排序后，设\(f_{i,j}\)表示考虑到第i个点，有父亲的点集合为j，有多少种方案。
转移时枚举儿子节点。
状态转移方程\(f_{i,j}=\sum_{k\subset j,sum(k)< w_i}f_{i-1,j-k}\)，其中\(sum(k)\)表示k集合内点聚合权值之和。
至于枚举一个二进制表示的集合j的子集k，可以通过这种方法：
- 我们得到了一个集合\(j\)。
- \(k=j\)
- \(k=(k-1)\& j\)
- 我们得到了一个集合\(k\)。
- if (k!=0) goto 2
就能得到所有子集。
复杂度为\(\sum_{i=0}^n\binom{n}{i}2^i=3^n\)
class HiddenTree {
public:
int f[1<<14];
ll sam[1<<14],tb[1<<14];
const int p=1000000007;
int lowbit(int x){return x&(-x);}
int count(vector<int> b) {
int n=b.size();
sort(all(b));
for(int i=0;i<n;++i)tb[1<<i]=b[i];
f[0]=1;
for(int i=1;i<(1<<n);++i){
sam[i]=sam[i^(lowbit(i))]+tb[lowbit(i)];
}
for(int i=1;i<n;++i){
for(int j=(1<<i)-1;j;--j){
int tpa=j;
for(int k=tpa;k;k=(k-1)&tpa){
if(sam[k]<b[i]){
(f[j]+=f[j^k])%=p;
}
}
}
}
int s=0;
for(int i=0;i<1<<n;++i)(s+=f[i])%=p;
return s;
}
};
SRM 724 1M
有一个游戏：在一个棋盘中，有一些格子里有木块。
当你按动上下左右时，所有的木块都会往对应方向移动直到无法移动为止。
给出终止状态，求可以通过按任意次键达到终止状态的初始状态数
我们发现按了右过几步按左是不如之前就按左。并且之前按了右几步后再按右是没有意义的。其它也一样。
所以最多2步就可以了。
对于终止状态，如果按左会变，则之前一定不能按左（先左再右这种之前说了毫无意义的不考虑）其它当然也一样。否则认为之前需要按左。
如果按左按右都不变，视为既不能按左有不能按右。（都毫无意义）上下相同。
如果左右上下都不能按，则答案为1.
如果有一个需要，假设为左，其它一样。
显然可以对于每行分开考虑。
假设这一行有m格，有k格有木块，显然有\(\binom{m}{k}\)种可行放木块方案。
乘起来就好了。
如果有两个，假设为上左。
有两种可能：先上再左，先左在上。
对于先上再左，我们首先把列重新排列，然后把每列弄散（就是只要上的情况）
先左再上反过来
然后去掉重复的：行重排再列重排
就可以了。
class GravityPuzzle {
public:
const int p=1000000007;
int hang[66],lie[66],fac[66],invf[66],inv[66],c[66][66];
int hs[66],ls[66];
int calc(int n,int m){
int han=fac[n],hanga=1,liea=1;
for(int i=0;i<n;++i){
++hs[hang[i]];
hanga=(long long)hanga*c[m][hang[i]]%p;
}
for(int i=0;i<=m;++i)han=(long long)han*invf[hs[i]]%p;
for(int i=0;i<m;++i){
++ls[lie[i]];
liea=(long long)liea*c[n][lie[i]]%p;
}
int li=fac[m];
for(int i=0;i<=n;++i)li=(long long)li*invf[ls[i]]%p;
int ansa=(long long)hanga*han%p,ansb=(long long)liea*li%p,ansc=(long long)han*li%p;
// printf("%d %d %d %d\n",han,hanga,li,liea);
return ((ansa+ansb-ansc)%p+p)%p;
}
int count(vector<string> board) {
int n=board.size(),m=board[0].length();
for(int i=0;i<n;++i)for(int j=0;j<m;++j)if(board[i][j]=='#')++hang[i],++lie[j];
// for(int i=0;i<n;++i)cout<<board[i]<<endl;
int t=50;
for(int i=0;i<=t;++i){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;++j)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
}
fac[0]=fac[1]=inv[1]=invf[0]=invf[1]=1;
for(int i=2;i<=t;++i){
fac[i]=((long long)fac[i-1]*i)%p;
inv[i]=(long long )(p-p/i)*(long long )inv[p%i]%p;
invf[i]=(long long)invf[i-1]*inv[i]%p;
}
int up=1,down=1,left=1,right=1;
for(int i=0;i<n;++i){
int j=0;
while(j<m&&board[i][j]=='#')++j;
left&=(j==hang[i]);
j=m;
while(j&&board[i][j-1]=='#')--j;
right&=(m-j==hang[i]);
}
for(int j=0;j<m;++j){
int i=0;
while(i<n&&board[i][j]=='#')++i;
up&=(i==lie[j]);
i=n;
while(i&&board[i-1][j]=='#')--i;
down&=(n-i==lie[j]);
}
int h=left^right;
int l=up^down;
if(h){
if(l){
return calc(n,m);
}
else{
int ans=1;
for(int i=0;i<n;++i){
ans=(long long)ans*c[m][hang[i]]%p;
}
return ans;
}
}
else{
if(l){
int ans=1;
for(int i=0;i<m;++i){
ans=ans*((long long)c[n][lie[i]])%p;
}
return ans;
}
else{
return 1;
}
}
return 0;
}
};SRM 722 1M
也包括2H
假设一个内核的计算力为S，当你使用k个内核的时候，计算力就为kS。完成一个任务的时间也就/k
但是由于调用需要时间，每多使用一个内核就要多花费P时间。
给出一个任务的工作量l，P还有多个CPU每个CPU的内核数C，算力S，请你选择一个CPU，选择使用的内核数，使得需要时间最少 （工作量/计算力+多耗费的时间），求出上取整的结果
对于2H可以直接暴力。
对于1M \(10^9\)的数据范围，似乎不行。
记\(f(c)\)表示用c个内核，如果增加一个内核需要的时间增加多少。
显然\(f(c)=\frac{len}{c+1}-\frac{len}{c}+P\)
由于反比例函数的性质，f(c)是递增的。那么一定有一个内核数C使得越减少时间越长，越增加时间也越长。此时\(f(C)>0\)并且\(f(C-1)\le 0\)，二分这个C即可。
class MulticoreProcessing {
public:
long long fastestTime(long long jobLength, int corePenalty, vector<int> speed, vector<int> cores) {
long long mintime=0x3f3f3f3f3f3f3f3f,att,n=speed.size(),speedd,coress;
for(int i=0;i<n;++i){
speedd=speed[i];coress=cores[i];
double faq=jobLength*1./speedd;
long long l=1,r=coress-1,mid;
while(l<=r){
mid=(l+r)>>1;
if(faq/mid>=faq/(mid+1)+corePenalty)l=mid+1;
else r=mid-1;
}
att=(l-1)*corePenalty;
att+=jobLength/speedd/l;
if(jobLength%(speedd*l))++att;
chkmin(mintime,att);
}
return mintime;
}
};SRM 721 1M
对于一个无向简单图G，设\(f(G)\)表示G图中最短路恰好为d的无序点对个数。
给定d,k，构造一个图G使得\(f(G)=k\)。
\(2\le d \le 50,1\le k\le 50000,|V|,|E|\le 1000\)
当d=2时，我们可以构造多个菊花图。
对于一个点数为\(d+1\)的菊花图，点对数是\(\frac{d(d-1)}{2}\)
每次找个最大的d，加上一个图,\(k-=\frac{d(d-1)}{2}\)，直到k=0
否则，我们可以构造一棵树：
中间有d-1个点连成，左边点连着a个点，右边点连着b个点。
就有ab 个点对了。
首先找到最大的d使得\(d^2\le k\)
建一棵左d右d的树。
剩下的点对数\(e \le 2d\)
建一个左1右e的树。
就可以了。
其它题目
SRM 728 1E
你有n个数，你想让它们相同。
现在你可以进行一个操作多次：选一个数，如果它是偶数就直接除2，否则，除2以后选择上取整或者下取整。
问最少需要多少次操作。
对每个数，用一个区间\([L_i,R_i]\)来表示它，意思原数通过修改可以变成这个区间内的数。
每次选取左界最大的区间\([L,R]\)，将其变成\([\lfloor \frac{L}{2}\rfloor,\lceil \frac{R}{2}\rceil]\) 直到所有区间两两相交为止，这时一定有公共交点，这个数就是最后得到的数。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
using namespace std;
class Halving {
public:
typedef pair<int,int> pii;
#define x first
#define y second
int have_same(vector<pii>::iterator be,vector<pii>::iterator ed){
for(vector<pii>::iterator i=be;i!=ed;++i)
for(vector<pii>::iterator j=i+1;j!=ed;++j)if(i->y<j->x)return 0;
return 1;
}
vector<pii> a;
int minSteps(vector<int> aa) {
for(vector<int>::iterator i=aa.begin();i!=aa.end();++i)a.push_back(make_pair(*i,*i));
sort(a.begin(),a.end());
int cnt=0;
while(!have_same(a.begin(),a.end())){
a.back().x>>=1;
(++(a.back().y))>>=1;
sort(a.begin(),a.end());
++cnt;
}
return cnt;
}
};SRM 726 2M
Hero和Jack（算了还是称为Alice和Bob吧）在玩一个游戏。
有一个n*m的棋盘，有些格子不能走，有些格子能走。
我们认为如果能仅通过向右和向下从左上角到右下角则这个棋盘是好的。
一开始棋盘是好的。
从Alice开始，每个人要选一个能走的格子将它标记为不可走。并且使这个棋盘仍为好的。
谁不能选谁输。
当然，两个人都绝顶聪明。
问Alice是否必胜。
发现一条可行路长度为n+m-1。
然后如果可走的格子数w-(n-m+1)是奇数则Alice必胜否则Bob必胜。
SRM 726 1E
有n袋糖果，第i袋标注有\(A_i\)颗A类糖果，\(B_i\)颗B类糖果。但是事实上有可能多个A少个B或者多个B少个A。价格\(C_i\)。
\(A_i,B_i,C_i,k\le 10000,n\le 50\)
现在希望买其中的一些袋使得一定会出现至少k颗同类糖果（可以是A也可以是B）
问最少花多少钱。
第\(i\)袋至少有\(A_i-1\)颗A，\(B_i-1\)颗B。总数一定是\(A_i+B_i\)
有3种可能：
1.可以保证有k颗A。
2.可以保证有k颗B。
3.可以保证有2k-1颗糖，此时根据抽屉原理至少有k颗同类糖。
如果都不可能满足直接不可能
由于价格最多5e5,所以可以\(O(n\sum C_i)\)DP。
\(f_t[i]\)表示对于第t种方案i元最多能有几颗满足条件的糖。
然后找到最小的i使得\(f_1[i]\ge A,f_2[i]\ge k,f_3[i]\ge 2k-1\)至少满足一项。就是答案。
SRM 721 2E
你从一个点开始，进行n次操作。每次形如向k方向行进a米。其中给出的方向是一个度数s，表示方向为从正北开始顺时针方向s度。问最后里原来多远。
以北为x轴正方向，东为y轴正方向，则向s方向a米会从原点走到\((a\cos s,a\sin s )\)，这样就能得到最终坐标。然后就能直接计算了。
SRM 721 1E & 2M
给定\(d_1,d_2,w_1,w_2\)，问能否构造一个长度为\(d_1+d_2\)的非负整数序列f（下标\(1\dots d1+d2\)），使得：
- \(\forall_{0\le i<d1+d2}|f_i-f_{i+1}|\le 1\)
- \(\sum_{i=1}^{d_1}f_i=w_1\)
- \(\sum_{i=1}^{d_2}f_{i+d_1}=w_2\)
对于2M，数据范围1000000，对于1E，数据范围\(10^9\)
我们可以枚举\(f_{d_1}\)，然后就变成了一个判断第0项为\(s\)（不算），长度为\(d\)，和能否为\(w\)的问题。
首先考虑上界。如果之后每个都+1,答案就是\(sd+\frac{d(d+1)}{2}\)
然后下界。考虑每个都-1。如果可以保证最后都不小于0，则就是\(sd-\frac{d(d+1)}{2}\)，否则就是减到为止\(\frac{s(s+1)}{2}\)
就能\(O(1)\)判断了。
然后考虑1E。
考虑每个序列，由于d固定，则\(sd+\frac{d(d+1)}{2}\)随s变化，要\(\ge w\)，就能解出s的范围区间。
下界要分类讨论，也能分别解出s的范围区间，这几个区间和这个讨论区间如果有并集则可以，否则不可以。
一共讨论4次（两个区间，两种可能）
2M：
class RememberWordsEasy {
public:
int okay(int daysum,int wordssum,int eachday){
long long now=wordssum,up;
now-=(long long)daysum*eachday;
up=daysum;
up*=(up+1);
up>>=1;
long long down=((daysum<=eachday)?(-up):(-(long long)daysum*eachday)+(long long)eachday*(eachday-1)/2);
// chkmax(down,-(long long)eachday*(eachday-1)/2-);
return (now<=up&&down<=now);
}
string isPossible(int d1, int d2, int w1, int w2) {
for(int i=0;i<=w1;++i){
if(okay(d1-1,w1-i,i)&&okay(d2,w2,i)){
return "Possible";
}
}
return "Impossible";
}
};1E：
class RememberWords {
public:
/*
if w<d1:
w(w+1)/2<=w1<=wd1+d1(d1-1)/2
else:
wd1-d1(d1-1)/2<=w1<=wd1+d1(d1-1)/2
if w<=d2:
w(w-1)/2<=w2<=wd2+d2(d2+1)/2
else:
wd2-d2(d2+1)/2<=w2<=wd2+d2(d2+1)/2
*/
#define x first
#define y second
ll ef(ll w){
ll l=1,r=w,mid;
while(l<=r){
mid=(l+r)>>1;
if(mid*(mid+1)>>1<=w)l=mid+1;
else r=mid-1;
}
return l-1;
}
ll getup(ll w,ll x,ll y){
w+=(x*y)/2;
w/=x;
return w;
}
ll getdown(ll w,ll x,ll y){
w-=(x*y)/2;
w=(w/x)+bool(w%x);
return w;
}
pii hb(pii a,pii b){
return pii(max(a.x,b.x),min(a.y,b.y));
}
string isPossible(ll d1, ll d2, ll w1, ll w2) {
ll aup1=ef(w1),bup1=ef(w2)+1,aup2=getup(w1,d1,d1-1),bup2=getup(w2,d2,d2+1),adown=getdown(w1,d1,d1-1),bdown=getdown(w2,d2,d2+1);
chkmax(adown,0);
chkmax(bdown,0);
pair<ll,ll> a1(adown,aup1),a2(adown,aup2),b1(bdown,bup1),b2(bdown,bup2),sa(0,d1-1),sb(0,d2),ta(d1,1000000007),tb(d2+1,1000000007);
pii hb1,hb2,hb3,hb4;
hb1=hb(hb(a1,b1),hb(sa,sb));
hb2=hb(hb(a1,b2),hb(sa,tb));
hb3=hb(hb(a2,b1),hb(ta,sb));
hb4=hb(hb(a2,b2),hb(ta,tb));
if(hb1.x<=hb1.y||hb2.x<=hb2.y||hb3.x<=hb3.y||hb4.x<=hb4.y)return "Possible";
else return "Impossible";
return "";
}
};