A .Secret of Chocolate Poles
题意：有黑白两种木块，黑色有1，K两种长度； 白色只有1一种长度，问满足黑白黑...白黑形式，长度为L的组合种类。
思路：直接DP即可。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
ll dp[][],ans;
int main()
{
int L,K;
scanf("%d%d",&L,&K);
dp[][]=;
rep(i,,L){
dp[i][]=dp[i-][];
dp[i][]=dp[i-][];
if(i-K>=) dp[i][]+=dp[i-K][];
}
rep(i,,L) ans+=dp[i][];
printf("%lld\n",ans);
return ;
}
B .Parallel Lines
题意：给定二维平面上N个点，N是偶数，限制让你两两连线，使得平行线对数最多。N<=16;
思路：N为16时，复杂度=15*13*11*9*7*5*3*1~=2e6；所以可以枚举所有情况，即搜索可以做。 注意是两两配对，没有不选的情况，不然复杂度很高。
统计时用了map带了个log。 这个log还可以优化掉，比如，变为每次加入一个斜率x时，res+=num[x]; num[x]++; 就不用map记录每个斜率的个数，最后才去统计答案了。
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int X[maxn],Y[maxn],ans,N,vis[maxn];
map<pii,int>mp; map<pii,int>::iterator it;
pii a[maxn][maxn];
void dfs(int pos)
{
if(pos==N+){
int res=;
for(it=mp.begin();it!=mp.end();it++){
res+=(it->second)*((it->second)-)/;
}
ans=max(ans,res);
return ;
}
if(!vis[pos])
for(int i=pos+;i<=N;i++){
if(!vis[i]){
vis[i]=;
mp[a[pos][i]]++;
dfs(pos+);
mp[a[pos][i]]--;
vis[i]=;
}
}
else dfs(pos+);
}
int main()
{
scanf("%d",&N);
rep(i,,N) scanf("%d%d",&X[i],&Y[i]);
rep(i,,N) rep(j,i+,N){
int dx=X[j]-X[i],dy=Y[j]-Y[i];
if(dx<) dx=-dx,dy=-dy;
if(dx==) dy=abs(dy);
int g=__gcd(dx,dy);
dx/=g; dy/=g;
a[i][j]=pii(dx,dy);
}
dfs();
printf("%d\n",ans);
return ;
}
C .Medical Checkup
题意：有有无限个医院，N个学生，第i个学生在每个医院检查的时间都一样，是hi。 他们排成一队去检查。 满足，一个医院不能同时检查多个人，一个人前面的那个人检查完后才能去检查， 给定时间T，问每个人在哪个医院里检查（或者在等候）。
思路：对思维题不感冒啊，想的过于复杂了。 这个题，对于所有的人都满足的东西是开始入队的时间是一定的，即h1+h2+...hi-1。
然后，从他开始检查开始，就把入队的看成一个整体，那么，这个整体的队尾前进的距离，取决于整个队伍前进的最小距离。
所以不难得出他们的答案=(T-h1-h2-...)/hi+2；
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
ll h[maxn];
int main()
{
int N; ll sum=,T,Mx=;
scanf("%d%lld",&N,&T);
rep(i,,N){
scanf("%lld",&h[i]);
Mx=max(Mx,h[i]);
sum+=h[i];
if(T>=sum) printf("%lld\n",(T-sum )/Mx+);
else printf("1\n");
}
return ;
}
E .Black or White
题意：给定一排，N个砖，只有黑白两色，给出它们初始的颜色S，限制你有长度为1到K的刷子，问至少刷多少次，可以把它们刷成给定状态T。
思路：假设一排长度为M的没有颜色砖，染色成BWBWBW..的形式，至少需要(M+1)/2+1刷子。 所以其实初始状态没有多大用处（除非相同），我们只考虑目标状态。
我们把T种相邻颜色相同的看成一个整体，那么：
dp[i]=dp[i-1]; 当s[i]==t[i];
dp[i]=dp[j]+(sum[i]-sum[j+1]+1)/2+1; 当s[i]!=t[i];
第二个方程直接单调队列可以搞。 如果我们考虑了初始状态，那么只会越想越复杂。
#include<bits/stdc++.h>
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=;
int dp[maxn],sum[maxn],q[maxn],head,tail,N,K;
char a[maxn],b[maxn];
int main()
{
scanf("%d%d",&N,&K);
scanf("%s%s",a+,b+);
rep(i,,N) sum[i]=sum[i-]+(b[i]!=b[i-]);
head=tail=; q[]=;
rep(i,,N){
if(a[i]==b[i]) dp[i]=dp[i-];
else
dp[i]=dp[q[head]]+(sum[i]-sum[q[head]+]+)/+;
while(tail>=head&&dp[i]*-sum[i+]<=dp[q[tail]]*-sum[q[tail]+]) tail--;
while(tail>=head&&i-q[head]>=K) head++;
q[++tail]=i;
}
printf("%d\n",dp[N]);
return ;
}
I .Starting a Scenic Railroad Service
题意：给定N个人的陆游线路，问自己选票的情况下，和售票方选票的情况下，旅游车需要多少个位置。
思路：反正题意差不多是这样，第一个问是问max(一个人的路线+和他规范相交的路线个数)。 第二个问是max(单点最大路线覆盖);
第二个问，由于数据小，可以用差分或者线段树； 如果数据大，可以直接排序做。 是个常规题了。
第一个问，和一个线段相交的线段个数，=N-在他前面的-在他后面的。 不难想到也可以差分去做。 数据大后还是可以排序来做。
覆盖问题，个人更喜欢写排序，因为不用考虑下标大小，或者离散化导致的边界问题。
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
pii a[maxn],b[maxn];
int A[maxn],B[maxn],ans1,ans2,tot;
int main()
{
int N,pre=; scanf("%d",&N);
rep(i,,N) {
scanf("%d%d",&a[i].f,&a[i].s);
b[++tot]=pii(a[i].f,);
b[++tot]=pii(a[i].s,-);
}
rep(i,,N){
A[a[i].f]++;
B[a[i].s]++;
}
rep(i,,) A[i]+=A[i-],B[i]+=B[i-];
rep(i,,N){
int f=B[a[i].f]+N-A[a[i].s-];
ans1=max(ans1,N-f);
}
sort(b+,b+tot+);
rep(i,,tot){
if(b[i].s==-) pre--;
else pre++;
ans2=max(ans2,pre);
}
printf("%d %d\n",ans1,ans2);
return ;
}
F .Pizza Delivery
题意：给定N点M边有向带权图，起点S=1，终点T=2； 对于每个边，问他转向后，起点到终点的最短路变大还是变小或者不变。
思路：首先肯定要两次SPFA，求出S和T到每个点的最短路，分别是dis1，dis2；
当且仅当，然后如果dis1[v]+dis2[u]+w[i]<dis1[T]，那么这条边可以让最短路变小。
否则，最短路变大或者不变，如果不变，说明最短路不是必经这条边。
那么本题的关键问题就是问边是否是最短路必经边。
我们把最短路上的边抽出来（就是满足dis1[u]+dis2[v]+w[i]==dis1[T]那些有向边，把它看成无向边），然后不难想到就是求“桥”。
如果桥转向了，那么最短路一定变长。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const ll inf=1LL<<;
struct dijst
{
struct in{
ll dis;int u;
in(){}
in(ll d,int uu):dis(d),u(uu){}
bool friend operator<(in w,in v){
return w.dis>v.dis;
}
};
ll dis[maxn]; int Len[maxn],cnt,S;
int Laxt[maxn],Next[maxn],inq[maxn],To[maxn];
void init(int N){
cnt=; rep(i,,N) inq[i]=Laxt[i]=,dis[i]=inf;
}
void add(int u,int v,int w){
Next[++cnt]=Laxt[u]; Laxt[u]=cnt;
To[cnt]=v; Len[cnt]=w;
}
void SPFA()
{
dis[S]=; priority_queue<in>q;
q.push(in(0LL,S));
while(!q.empty())
{
int u=q.top().u; q.pop(); inq[u]=;
for(int i=Laxt[u];i;i=Next[i]){
int v=To[i];
if(dis[v]>dis[u]+Len[i]){
dis[v]=dis[u]+Len[i];
if(!inq[v]) inq[v]=,q.push(in(dis[v],v));
}
}
}
}
}D1,D2;
int a[maxn],b[maxn],c[maxn],cnt;
int dfn[maxn],low[maxn],times,Br[maxn];
int Laxt[maxn],Next[maxn],To[maxn],id[maxn];
void add(int u,int v,int p)
{
Next[++cnt]=Laxt[u]; Laxt[u]=cnt;
To[cnt]=v; id[cnt]=p;
}
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++times;
for(int i=Laxt[u];i;i=Next[i]){
int v=To[i];
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]) Br[id[i]]=;
}
else if(v!=fa) low[u]=min(low[u],dfn[v]);
}
}
int main()
{
int N,M;
scanf("%d%d",&N,&M);
D1.init(N); D2.init(N);
D1.S=; D2.S=;
rep(i,,M) {
scanf("%d%d%d",&a[i],&b[i],&c[i]);
D1.add(a[i],b[i],c[i]);
D2.add(b[i],a[i],c[i]);
}
D1.SPFA(); D2.SPFA(); ll Dis=D1.dis[];
rep(i,,M){
if(D1.dis[a[i]]+D2.dis[b[i]]+c[i]==Dis){
add(a[i],b[i],i);
add(b[i],a[i],i);
}
}
rep(i,,N) if(!dfn[i]) tarjan(i,);
rep(i,,M){
if(D1.dis[b[i]]+D2.dis[a[i]]+c[i]<Dis) printf("HAPPY\n");
else if(Br[i]) printf("SAD\n");
else printf("SOSO\n");
}
return ;
}