题目
传送门：QWQ
A：Codehorses T-shirts
题意：
给定一些字符串表示去年和今年的衣服型号大小( XL XXL M...... )，要求用最少的次数把去年的衣服大小改成今年需要的。每次改动只能更改字符，不能增添字符。
分析：
把今年和去年的型号字典序排一下。然后用挨个对上（因为题目保证合法，所以长度一样的数量必定相等）。在字符串长度是1的时候要暴力匹配一下，因为长度为1时有L S M三种东西。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=;
string a[maxn], b[maxn], q1[maxn], q2[maxn];
int vis[maxn];
int main(){
int n; scanf("%d",&n);
for(int i=;i<=n;i++) cin>>a[i];
for(int i=;i<=n;i++) cin>>b[i];
sort(a+,a++n);sort(b+,b++n);
int ans=;
for(int i=;i<=n;i++){
if(a[i].length()==) continue;
for(int j=;j<a[i].length();j++)
{
if(a[i][j]!=b[i][j]) ans++;
}
}
int k=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(a[i].length()!=||b[j].length()!=) continue;
if(a[i]==b[j] && vis[j]==) {
vis[j]=; k--; break;
}
}
for(int i=;i<=n;i++) if(a[i].length()==) k++;
printf("%d\n",ans+k);
return ;
}
B：Light It Up
题意：
给定一个$ 10^18 $ 次方的数轴，在数轴上有一些点表示时间。其中有端点0和M。随着时间的推移，每到一个时间点就改变等的状态。
你可以新插入一个点（或者不插），求插入后总的灯亮的时间。
分析：
显然我插的点肯定是在给的点左一个或右一个·。然后前缀和优化模拟一下。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
ll A1[maxn],A2[maxn];
ll M[maxn],maxans;ll sum=;
int main(){
int n;ll m;scanf("%d%I64d",&n,&m);
memset(A1,,sizeof(A1));memset(A2,,sizeof(A2));memset(M,,sizeof(M));
M[]=;M[n+]=m;
for(int i=;i<=n+;i++){
scanf("%I64d",&M[i]);
}
M[n+]=M[n+];
for(int i=;i<=n+;i+=){
A1[i-]=A1[i-];
A1[i]+=A1[i-]+M[i+]-M[i];
}A1[n+]=A1[n+];
for(int i=;i<=n+;i+=){
A2[i-]=A2[i-];
A2[i]+=A2[i-]+M[i+]-M[i];
}
A2[n+]=A2[n+];
for(int i=;i<=n+;i++){
ll ma1,ma2;
if(i%== && M[i]!=M[i-]+){
ma1=A1[i-]-+(A2[n+]-A2[i-]);
ma2=A1[i]-+(A2[n+]-A2[i-]);
}
else if(M[i]!=M[i+]-){
ma1=A1[i-]-+(A2[n+]-A2[i-]);
ma2=A1[i]-+(A2[n+]-A2[i-]);
}
if(i!=) maxans=max(maxans,max(ma1,ma2));
else maxans=ma2;
}
printf("%I64d\n",max(A1[n+],maxans));
return ;
}
C：Covered Points Count
题意：
线段覆盖数轴相关
分析：
大力算一下，如果是左端点就ans++，否则ans--
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
ll sum[maxn];
struct Node{
ll a;int type;
bool operator < (const Node& b) const{return a<b.a;}
}A[maxn];
int main(){
int n,cnt=;scanf("%d",&n);
ll l,r;
for(int i=;i<=n;i++){
scanf("%I64d%I64d",&l,&r);
A[++cnt].a=l; A[cnt].type=; A[++cnt].a=r+; A[cnt].type=-;
}
sort(A+,A++cnt);
A[].a=A[].a;
int ans=,preans=;
for(int i=;i<=cnt;i++){
preans=ans; ans+=A[i].type;
sum[preans]+=A[i].a-A[i-].a;
}
for(int i=;i<=n;i++){
printf("%I64d ",sum[i]);
}
return ;
}
/*
5
10000000000 20000000000
10 100000000000000000
10 100000000000000000
10 100000000000000000
10 100000000000000000
*/
D：Yet Another Problem On a Subsequence
题意：
如果一个数组$ a_1.......a_k $ 且 $ a_1 = k-1$，辣么这个数组就是好数组。
一个好序列由好序列和（或）好数组组成。
给出一序列，求他有多少子序列是好序列。
分析：
很显然想到组合数计数一下，但不好处理子序列这个问题。
用$ dp[i] $表示以i开头的好序列的数量
然后对于每个$ a[i] $更新$ dp $
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2000l;const ll MOD=;
ll C[maxn][maxn], a[maxn], dp[maxn];
int main(){
int n;scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%I64d",&a[i]); for(int i=;i<=n+;i++)
for(int j=;j<=n+;j++){
if(j==) C[i][j]=i;
else C[i][j]=(C[i-][j]+C[i-][j-])%MOD;
} dp[n+]=;
for(int i=n-;i>=;i--){
if(a[i]<= || a[i]+i>n) continue;
for(int j=i+a[i]+;j<=n+;j++){
dp[i]=(dp[i]+C[j-i-][a[i]]*dp[j])%MOD;
}
} ll ans=;
for(int i=;i<=n;i++){
ans=(ans+dp[i])%MOD;
}
printf("%I64d\n",ans);
return ;
}
E：We Need More Bosses
题意：
求一张图桥最多的路径上桥的数量
分析：
缩点后求树的直径
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=;
struct Edge{ int u,v; };
vector<Edge> edges; vector<int> G[maxn], g[maxn];
int n, m ;
void Addedge(int a,int b){
edges.push_back((Edge){a,b}); edges.push_back((Edge){b,a});
int m=edges.size(); G[a].push_back(m-);G[b].push_back(m-);
}
int dfs_clock, low[maxn], pre[maxn], q[maxn], fron, scc_cnt, scc[maxn];
int dfs(int u,int fa){
int lowu=pre[u]=++dfs_clock;
q[++fron]=u;
for(int i=;i<G[u].size();i++){
int v=edges[G[u][i]].v, lowv;
if(u==fa) continue;
if(!pre[v]){
lowv=dfs(v,u); lowu=min(lowu,lowv);
// if(lowv>=pre[u]){ ok[G[u][i]]=1; ok[G[u][i]^1]=1;}
}
else{
if(pre[v]<pre[u] && v!=fa) lowu=min(lowu,pre[v]);
}
}
low[u]=lowu;
if(pre[u]==low[u]){
scc_cnt++;
for(;;){
int x=q[fron--]; scc[x]=scc_cnt;
if(x==u) break;
}
}
return lowu;
}
queue<int> que;
int dis[maxn], inq[maxn];
void dist(int x,int f){
dis[x]=dis[f]+;
for(int i=;i<g[x].size();i++){ int v=g[x][i]; if(v==f) continue;//printf("============ %d\n",v);
dist(v,x);
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y); Addedge(x,y);
}
dfs(,-);
for(int i=;i<edges.size();i++){
Edge e=edges[i];
// printf("--------- %d %d\n",scc[e.u],scc[e.v]);
if(scc[e.u]!=scc[e.v]) g[scc[e.u]].push_back(scc[e.v]);
}
dist(,);int mx=,mp=;
for(int i=;i<=scc_cnt;i++){
if(dis[i]>mx) mx=dis[i],mp=i;
}
memset(dis,,sizeof(dis));
dist(mp,); mx=;
for(int i=;i<=scc_cnt;i++) mx=max(mx,dis[i]);
printf("%d\n",mx-);
return ;
}