找了一些比较水的cf上的题目，然而又不想整套整套的的写了，于是一些散的cf上的题目就放在这里了。

现在做了几题：

好弱啊、、

427B.Prison Transfer

题意：给定长度为n的一个序列，和c，t两个数字。问你有多少个连续的长度为c的子串，且序列中最大数不超过t。 $1\leq n,c\leq10^{5},1\leq a_{i},t\leq 10^{9}$

题解：直接扫一遍。

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
template <class T>
inline void read(T &res){
    char c;res=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9'){
        res=res*10+(c-'0');
        c=getchar();
    }
}
/////////
int a[maxn];
int n,c,t;
int main()
{
    read(n);read(t);read(c);
    for(int i=1;i<=n;i++) read(a[i]);
    int ans=0,pos=0;
    for(int i=1;i<=n;i++){
        if(a[i]>t) pos=0;
        else{
            pos++;
            if(pos>=c) ans++;
        }
    }
    printf("%d\n",ans);
}

#include <bits/stdc++.h>

#define maxn 200010

using namespace std;

template <class T>

inline void read(T &res){

char c;res=0;

while((c=getchar())<'0'||c>'9');

while(c>='0'&&c<='9'){

res=res*10+(c-'0');

c=getchar();

}

/////////

int a[maxn];

int n,c,t;

int main()

{

read(n);read(t);read(c);

for(int i=1;i<=n;i++) read(a[i]);

int ans=0,pos=0;

for(int i=1;i<=n;i++){

if(a[i]>t) pos=0;

else{

pos++;

if(pos>=c) ans++;

}

printf("%d\n",ans);

}

475B.Strongly Connected City

给出n条水平的单向道路，m条竖直的单向道路。问形成的n*m个节点是否都可以互相可达。 $1\leq n,m\leq20,%1\leq a_{i},t\leq 10^{9}$

题解：tarjan求一下整个图是否为一个强连通分量。

#include <bits/stdc++.h>
#define maxn 500
using namespace std;
typedef long long ll;
int n,m;
vector<int>e[maxn];
int pre[maxn],low[maxn],dfs_clock,scc_cnt,sccno[maxn];
stack<int>S;
void dfs(int st){
    pre[st]=low[st]=(++dfs_clock);
    S.push(st);
    for(int i=0;i<e[st].size();i++){
        int Next=e[st][i];
        if(!pre[Next]){
            dfs(Next);
            low[st]=min(low[st],low[Next]);
        }
        else if(!sccno[Next]){
            low[st]=min(low[st],pre[Next]);
        }
    }
    if(low[st]==pre[st]){
        scc_cnt++;
        while(1){
            int now=S.top();S.pop();
            sccno[now]=scc_cnt;
            if(now==st) break;
        }
    }
}
void Tarjan(){
    dfs_clock=scc_cnt=0;
    memset(pre,0,sizeof(pre));memset(sccno,0,sizeof(sccno));
    for(int i=1;i<=n*m;i++)
        if(!pre[i]) dfs(i);
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        char ch;scanf(" %c",&ch);
        if(ch=='<'){
            for(int j=1;j<m;j++){
                int u=(i-1)*m+j;
                int v=(i-1)*m+j+1;
                e[v].push_back(u);
            }
        }
        else if(ch=='>'){
            for(int j=1;j<m;j++){
                int u=(i-1)*m+j;
                int v=(i-1)*m+j+1;
                e[u].push_back(v);
            }
        }
    }
    for(int i=1;i<=m;i++){
        char ch;scanf(" %c",&ch);
        if(ch=='^'){
            for(int j=1;j<n;j++){
                int u=(j-1)*m+i;
                int v=j*m+i;
                e[v].push_back(u);
            }
        }
        else if(ch=='v'){
            for(int j=1;j<n;j++){
                int u=(j-1)*m+i;
                int v=j*m+i;
                e[u].push_back(v);
            }
        }
    }
    Tarjan();
    int flag=sccno[1];
    bool ok=true;
    for(int i=2;i<=n*m;i++){
        if(flag!=sccno[i])  ok=0;
    }
    if(ok) puts("YES");
    else puts("NO");
}

#include <bits/stdc++.h>

#define maxn 500

using namespace std;

typedef long long ll;

int n,m;

vector<int>e[maxn];

int pre[maxn],low[maxn],dfs_clock,scc_cnt,sccno[maxn];

stack<int>S;

void dfs(int st){

pre[st]=low[st]=(++dfs_clock);

S.push(st);

for(int i=0;i<e[st].size();i++){

int Next=e[st][i];

if(!pre[Next]){

dfs(Next);

low[st]=min(low[st],low[Next]);

}

else if(!sccno[Next]){

low[st]=min(low[st],pre[Next]);

}

if(low[st]==pre[st]){

scc_cnt++;

while(1){

int now=S.top();S.pop();

sccno[now]=scc_cnt;

if(now==st) break;

}

void Tarjan(){

dfs_clock=scc_cnt=0;

memset(pre,0,sizeof(pre));memset(sccno,0,sizeof(sccno));

for(int i=1;i<=n*m;i++)

if(!pre[i]) dfs(i);

}

int main()

{

scanf("%d %d",&n,&m);

for(int i=1;i<=n;i++){

char ch;scanf(" %c",&ch);

if(ch=='<'){

for(int j=1;j<m;j++){

int u=(i-1)*m+j;

int v=(i-1)*m+j+1;

e[v].push_back(u);

}

else if(ch=='>'){

for(int j=1;j<m;j++){

int u=(i-1)*m+j;

int v=(i-1)*m+j+1;

e[u].push_back(v);

}

for(int i=1;i<=m;i++){

char ch;scanf(" %c",&ch);

if(ch=='^'){

for(int j=1;j<n;j++){

int u=(j-1)*m+i;

int v=j*m+i;

e[v].push_back(u);

}

else if(ch=='v'){

for(int j=1;j<n;j++){

int u=(j-1)*m+i;

int v=j*m+i;

e[u].push_back(v);

}

Tarjan();

int flag=sccno[1];

bool ok=true;

for(int i=2;i<=n*m;i++){

if(flag!=sccno[i]) ok=0;

}

if(ok) puts("YES");

else puts("NO");

}

510C.Fox And Names

题意：给出n个字符串，问是否存在一个字母表，使得这n个字符串满足字典序。 $1\leq n,\left | s \right |\leq100,%1\leq a_{i},t\leq 10^{9}$

题解：字典序其实就是一种拓扑关系。那么根据字符串的关系，判断是否可以建立一个拓扑图即可。

#include <bits/stdc++.h>
#define maxn 30
using namespace std;
typedef long long ll;
vector<int>e[maxn];
int n;
char ss[211][211];
int in[maxn],vis[maxn];
int ans[maxn];
bool toposort(){
    queue<int>que;
    for(int i=1;i<=26;i++){
        if(!in[i]){
            vis[i]=1;
            que.push(i);
        }
    }
    int cnt=0;
    while(!que.empty()){
        int now=que.front();que.pop();
        ans[++cnt]=now;
        for(int i=0;i<e[now].size();i++){
            in[e[now][i]]--;
            if(in[e[now][i]]==0&&vis[e[now][i]]==0){
                vis[e[now][i]]=1;
                que.push(e[now][i]);
            }
        }
    }
    for(int i=1;i<=26;i++) if(!vis[i]) return 1;
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf(" %s",ss[i]);
    bool flag=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int len1=strlen(ss[i]);int len2=strlen(ss[j]);
            for(int k=0;k<len1;k++){
                if(k>len2-1) {flag=1;break;}
                if(ss[i][k]!=ss[j][k]){
                    int u=ss[i][k]-'a'+1;
                    int v=ss[j][k]-'a'+1;
                    e[u].push_back(v);
                    in[v]++;break;
                }
            }
        }
        if(flag) break;
    }
    if(!flag) flag=toposort();
    if(flag) puts("Impossible");
    else {
        for(int i=1;i<=26;i++)
            printf("%c",(char)(ans[i]+'a'-1));
        puts("");
    }
}

#include <bits/stdc++.h>

#define maxn 30

using namespace std;

typedef long long ll;

vector<int>e[maxn];

int n;

char ss[211][211];

int in[maxn],vis[maxn];

int ans[maxn];

bool toposort(){

queue<int>que;

for(int i=1;i<=26;i++){

if(!in[i]){

vis[i]=1;

que.push(i);

}

int cnt=0;

while(!que.empty()){

int now=que.front();que.pop();

ans[++cnt]=now;

for(int i=0;i<e[now].size();i++){

in[e[now][i]]--;

if(in[e[now][i]]==0&&vis[e[now][i]]==0){

vis[e[now][i]]=1;

que.push(e[now][i]);

}

for(int i=1;i<=26;i++) if(!vis[i]) return 1;

return 0;

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

scanf(" %s",ss[i]);

bool flag=0;

for(int i=1;i<=n;i++){

for(int j=i+1;j<=n;j++){

int len1=strlen(ss[i]);int len2=strlen(ss[j]);

for(int k=0;k<len1;k++){

if(k>len2-1) {flag=1;break;}

if(ss[i][k]!=ss[j][k]){

int u=ss[i][k]-'a'+1;

int v=ss[j][k]-'a'+1;

e[u].push_back(v);

in[v]++;break;

}

if(flag) break;

}

if(!flag) flag=toposort();

if(flag) puts("Impossible");

else {

for(int i=1;i<=26;i++)

printf("%c",(char)(ans[i]+'a'-1));

puts("");

}

437C.The Child and Toy

题意：给出n个节点，m条无向边，删除一个点的代价是与这个点相邻的还未被删除的点的点权和。问删除所有点的最小代价。

题解：贪心。很明显应该先删除点权最大的点。那么从大网小删即可。

#include <bits/stdc++.h>
#define maxn 1050
using namespace std;
typedef long long ll;
template <class T>
inline void read(T &res){
    char c;res=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9'){
        res=res*10+(c-'0');
        c=getchar();
    }
}
////////
int n,m;
bool des[maxn];
struct P{
    int val,id;
    P(){}
    P(int _x,int _y):val(_x),id(_y){}
}pp[maxn];
bool cmp(const P& a,const P& b){
    return a.val<b.val;
}
int ma[maxn];
vector<int>e[maxn];
int main()
{
    read(n);read(m);
    for(int i=1;i<=n;i++) {
        read(pp[i].val),pp[i].id=i;
        ma[i]=pp[i].val;
    }
    sort(pp+1,pp+1+n,cmp);
    for(int i=1;i<=m;i++){
        int u,v;read(u);read(v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    ll ans=0;
    for(int i=n;i;i--){
        int pos=pp[i].id;
        des[pos]=1;
        for(int j=0;j<e[pos].size();j++){
            if(des[e[pos][j]]) continue;
            ans+=ma[e[pos][j]];
        }
    }
    printf("%I64d\n",ans);
}

#include <bits/stdc++.h>

#define maxn 1050

using namespace std;

typedef long long ll;

template <class T>

inline void read(T &res){

char c;res=0;

while((c=getchar())<'0'||c>'9');

while(c>='0'&&c<='9'){

res=res*10+(c-'0');

c=getchar();

}

////////

int n,m;

bool des[maxn];

struct P{

int val,id;

P(){}

P(int _x,int _y):val(_x),id(_y){}

}pp[maxn];

bool cmp(const P& a,const P& b){

return a.val<b.val;

}

int ma[maxn];

vector<int>e[maxn];

int main()

{

read(n);read(m);

for(int i=1;i<=n;i++) {

read(pp[i].val),pp[i].id=i;

ma[i]=pp[i].val;

}

sort(pp+1,pp+1+n,cmp);

for(int i=1;i<=m;i++){

int u,v;read(u);read(v);

e[u].push_back(v);

e[v].push_back(u);

}

ll ans=0;

for(int i=n;i;i--){

int pos=pp[i].id;

des[pos]=1;

for(int j=0;j<e[pos].size();j++){

if(des[e[pos][j]]) continue;

ans+=ma[e[pos][j]];

}

printf("%I64d\n",ans);

}

500A.New Year Transportation

题意：有n个城市1排，从第i个城市可以走到i+a[i]号城市，给一个城市t，问是否能从1到t？
题解：从1开始扫一遍打标记，比如i打上标记，那么i+a[i]也打上标记。看最后t有没有被打上标记即可。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
template <class T>
inline void read(T &res){
    char c;res=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9'){
        res=res*10+(c-'0');
        c=getchar();
    }
}
//////
int a[30100];
bool vis[30100];
int main()
{
    int n,t;read(n);read(t);
    for(int i=1;i<n;i++) read(a[i]);
    vis[1]=1;
    for(int i=1;i<=n;i++){
        if(vis[i])
            vis[i+a[i]]=1;
    }
    if(vis[t]) puts("YES");
    else puts("NO");
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template <class T>

inline void read(T &res){

char c;res=0;

while((c=getchar())<'0'||c>'9');

while(c>='0'&&c<='9'){

res=res*10+(c-'0');

c=getchar();

}

//////

int a[30100];

bool vis[30100];

int main()

{

int n,t;read(n);read(t);

for(int i=1;i<n;i++) read(a[i]);

vis[1]=1;

for(int i=1;i<=n;i++){

if(vis[i])

vis[i+a[i]]=1;

}

if(vis[t]) puts("YES");

else puts("NO");

}

519B. A and B and Compilation Errors（模拟）

题意：给出三个序列下面的序列是上面的序列去掉一个数得到的。求出两个去掉的数。

$1\leq n \leq 10^{5},1 \leq ai,bi,ci \leq 10^{9}$

煞笔题。。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
template <class T>
inline void read(T &res){
    char c;res=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9'){
        res=res*10+(c-'0');
        c=getchar();
    }
}
/////
typedef long long ll;
ll sum1,sum2,sum3;
int main()
{
    int n;read(n);
    for(int i=1;i<=n;i++){
        int tmp;read(tmp);sum1+=(ll)tmp;
    }
    for(int i=1;i<=n-1;i++){
        int tmp;read(tmp);sum2+=(ll)tmp;
    }
    for(int i=1;i<=n-2;i++){
        int tmp;read(tmp);sum3+=(ll)tmp;
    }
    printf("%I64d\n",sum1-sum2);
    printf("%I64d\n",sum2-sum3);
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template <class T>

inline void read(T &res){

char c;res=0;

while((c=getchar())<'0'||c>'9');

while(c>='0'&&c<='9'){

res=res*10+(c-'0');

c=getchar();

}

/////

typedef long long ll;

ll sum1,sum2,sum3;

int main()

{

int n;read(n);

for(int i=1;i<=n;i++){

int tmp;read(tmp);sum1+=(ll)tmp;

}

for(int i=1;i<=n-1;i++){

int tmp;read(tmp);sum2+=(ll)tmp;

}

for(int i=1;i<=n-2;i++){

int tmp;read(tmp);sum3+=(ll)tmp;

}

printf("%I64d\n",sum1-sum2);

printf("%I64d\n",sum2-sum3);

}

639B. Bear and Forgotten Tree 3（构造乱搞）

题意：构造一棵 $n$ 个节点，直径为 $d$ ，深度为 $h$ 的树（深度是从1号节点算起）。

题解：判掉一些无解的情况。对于合法的的情况先从1连一条长度为h的链，然后再从1连一条长度为d-h的链，最后把剩下的点都连到根上。（这里有一个坑，如果h=d的话不能连1号节点）。细节挺多的，直接上代码了。

#include <bits/stdc++.h>
#define maxn 100010
#define inf 0x3f3f3f3f

using namespace std;
typedef long long ll;
template <class T>
inline void read(T &res){
    char c;res=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9'){
        res=res*10+(c-'0');
        c=getchar();
    }
}
///////
int n,d,h;
int fa[maxn];
int main()
{
    read(n);read(d);read(h);
    if(n<d+1||2*h+1<d+1||d+1<h+1||(d==1&&n>2)) {puts("-1");return 0;}
    for(int i=2;i<=h+1;i++) fa[i]=i-1;
    if(d==h)
        for(int i=d+2;i<=n;i++) fa[i]=2;
    else {
        fa[h+2]=1;
        for(int i=h+3;i<=d+1;i++) fa[i]=i-1;
        for(int i=d+2;i<=n;i++) fa[i]=1;
    }
    for(int i=n;i>1;i--)
        printf("%d %d\n",fa[i],i);
}

#include <bits/stdc++.h>

#define maxn 100010

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

template <class T>

inline void read(T &res){

char c;res=0;

while((c=getchar())<'0'||c>'9');

while(c>='0'&&c<='9'){

res=res*10+(c-'0');

c=getchar();

}

///////

int n,d,h;

int fa[maxn];

int main()

{

read(n);read(d);read(h);

if(n<d+1||2*h+1<d+1||d+1<h+1||(d==1&&n>2)) {puts("-1");return 0;}

for(int i=2;i<=h+1;i++) fa[i]=i-1;

if(d==h)

for(int i=d+2;i<=n;i++) fa[i]=2;

else {

fa[h+2]=1;

for(int i=h+3;i<=d+1;i++) fa[i]=i-1;

for(int i=d+2;i<=n;i++) fa[i]=1;

}

for(int i=n;i>1;i--)

printf("%d %d\n",fa[i],i);

}

298A. Snow Footprints（模拟+分类讨论）

题意不想说了。。。

只会出现RRLL，RRRR，LLLL这样的序列。而且注意是跨过这个格子，才会留下脚印。然后分类讨论一下。。。做这种字符串的分类讨论题目太恶心了。。。

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
char s[maxn];
int main()
{
    int n;scanf("%d",&n);
    scanf("%s",s+1);
    int flags=0,flagt=0;
    int ss=0,t=0;
    for(int i=1;i<=n;i++){
        if(flags&&s[i]=='R'&&s[i+1]=='.'){
            t=i+1;
            break;
        }
        if(s[i]=='R'&&s[i+1]=='L'){
            t=i;flagt=1;
        }
        if(s[i]=='R'&&flags==0){
            flags=1;
            ss=i;
        }
        if(s[i]=='.'&&flags&&(!flagt)){
            t=i;
            break;
        }
        if(s[i]=='L'&&flagt==0){
            flagt=1;
            t=i-1;
        }
        if(s[i]=='.'&&flagt&&(!flags)){
            ss=i-1;
            break;
        }
    }
    cout<<ss<<" "<<t<<endl;
}

#include <bits/stdc++.h>

#define maxn 1005

using namespace std;

char s[maxn];

int main()

{

int n;scanf("%d",&n);

scanf("%s",s+1);

int flags=0,flagt=0;

int ss=0,t=0;

for(int i=1;i<=n;i++){

if(flags&&s[i]=='R'&&s[i+1]=='.'){

t=i+1;

break;

}

if(s[i]=='R'&&s[i+1]=='L'){

t=i;flagt=1;

}

if(s[i]=='R'&&flags==0){

flags=1;

ss=i;

}

if(s[i]=='.'&&flags&&(!flagt)){

t=i;

break;

}

if(s[i]=='L'&&flagt==0){

flagt=1;

t=i-1;

}

if(s[i]=='.'&&flagt&&(!flags)){

ss=i-1;

break;

}

cout<<ss<<" "<<t<<endl;

}

298B. Sail（模拟+贪心）

题意不想说了。

显然对于当前位置，在一个时刻只有跟着风向走还是不走这两种选择。那么肯定要选择可以让我们离终点更近的选择了。把整个过程模拟一遍。

#include <bits/stdc++.h>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
char s[maxn];
int main()
{
    int t,sx,sy,ex,ey;
    scanf("%d %d %d %d %d",&t,&sx,&sy,&ex,&ey);
    scanf(" %s",s+1);
    int flag=-1;
    for(int i=1;i<=t;i++){
        if(s[i]=='S'&&sy>ey) sy-=1;
        if(s[i]=='E'&&sx<ex) sx+=1;
        if(s[i]=='W'&&sx>ex) sx-=1;
        if(s[i]=='N'&&sy<ey) sy+=1;
        if(sx==ex&&sy==ey) {
            printf("%d\n",i);break;
        }
    }
    if(sx!=ex||sy!=ey) puts("-1");
}

#include <bits/stdc++.h>

#define maxn 100005

#define inf 0x3f3f3f3f

using namespace std;

char s[maxn];

int main()

{

int t,sx,sy,ex,ey;

scanf("%d %d %d %d %d",&t,&sx,&sy,&ex,&ey);

scanf(" %s",s+1);

int flag=-1;

for(int i=1;i<=t;i++){

if(s[i]=='S'&&sy>ey) sy-=1;

if(s[i]=='E'&&sx<ex) sx+=1;

if(s[i]=='W'&&sx>ex) sx-=1;

if(s[i]=='N'&&sy<ey) sy+=1;

if(sx==ex&&sy==ey) {

printf("%d\n",i);break;

}

if(sx!=ex||sy!=ey) puts("-1");

}

382C. Arithmetic Progression（分类讨论）

题意：给出一个长度为n（n<1e5）的正数序列，每个数不超过1e8，然后你现在可以加入一个数让整个数列变成等差数列。有无数种方案输出-1，无解输出0.别的话输出方案数，以及添加的数。添加的数可以超过1e8或者是负数。

还是分类讨论。。。太恶心了。我们先计算出原数列的间距个数，以及间距大小。

1.如果只有一个数字，那么有无穷多解。

2.如果有三个或者以上间距一定无解。

3.只有一个间距的话。如果间距为0，也就是所有数都相同，那么只有一种方案。如果间距不为0而且这个序列的长度为2而且这个间距可以被2整除，那么有三种方案（因为可以放到中间）。否则只有两种。

4.有两个间距。如果较大的那个间距是较小的那个的两倍，较小的间距不能为0.而且较大间距的个数只有1个，那么有1种方案。

#include <bits/stdc++.h>

using namespace std;
int n;
int a[100010];
map<int,int>ma;
int cnt[100010];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    if(n==1) {puts("-1");return 0;}
    int pos=0;
    for(int i=2;i<=n;i++){
        if(ma[a[i]-a[i-1]]==0){
            ma[a[i]-a[i-1]]++;
            pos++;
            cnt[pos]=a[i]-a[i-1];
        }
        else ma[a[i]-a[i-1]]++;
    }
    if(pos>=3) {puts("0");return 0;}
    if(pos==2){
        int tmp=cnt[1];int tmp2=cnt[2];
        if(tmp2<tmp) swap(tmp,tmp2);
        if(tmp==0) {puts("0");return 0;}
        if(tmp2%tmp==0&&tmp2/tmp==2&&ma[tmp2]==1){
            printf("1\n");
            for(int i=2;i<=n;i++){
                if(a[i]-a[i-1]==tmp2){
                    printf("%d\n",a[i-1]+tmp2/2);
                }
            }
        }
        else puts("0");
    }
    if(pos==1){
        if(cnt[pos]==0) {
            puts("1");
            printf("%d\n",a[1]);
            return 0;
        }
        if(n==2){
            if(cnt[pos]%2==0){
                printf("3\n");
                printf("%d %d %d\n",a[1]-cnt[pos],a[1]+cnt[pos]/2,a[2]+cnt[pos]);
            }
            else {
                puts("2");
                printf("%d %d\n",a[1]-cnt[pos],a[2]+cnt[pos]);
            }
        }
        else {
            puts("2");
            printf("%d %d\n",a[1]-cnt[pos],a[n]+cnt[pos]);
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

int n;

int a[100010];

map<int,int>ma;

int cnt[100010];

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

sort(a+1,a+1+n);

if(n==1) {puts("-1");return 0;}

int pos=0;

for(int i=2;i<=n;i++){

if(ma[a[i]-a[i-1]]==0){

ma[a[i]-a[i-1]]++;

pos++;

cnt[pos]=a[i]-a[i-1];

}

else ma[a[i]-a[i-1]]++;

}

if(pos>=3) {puts("0");return 0;}

if(pos==2){

int tmp=cnt[1];int tmp2=cnt[2];

if(tmp2<tmp) swap(tmp,tmp2);

if(tmp==0) {puts("0");return 0;}

if(tmp2%tmp==0&&tmp2/tmp==2&&ma[tmp2]==1){

printf("1\n");

for(int i=2;i<=n;i++){

if(a[i]-a[i-1]==tmp2){

printf("%d\n",a[i-1]+tmp2/2);

}

else puts("0");

}

if(pos==1){

if(cnt[pos]==0) {

puts("1");

printf("%d\n",a[1]);

return 0;

}

if(n==2){

if(cnt[pos]%2==0){

printf("3\n");

printf("%d %d %d\n",a[1]-cnt[pos],a[1]+cnt[pos]/2,a[2]+cnt[pos]);

}

else {

puts("2");

printf("%d %d\n",a[1]-cnt[pos],a[2]+cnt[pos]);

}

else {

puts("2");

printf("%d %d\n",a[1]-cnt[pos],a[n]+cnt[pos]);

}

450D. Jzzhu and Cities（最短路）

题目大意：在一个国家中有n个城市（城市编号1~n），m条公路，k条铁路，编号为1的城市为首都，为了节约，不需要的铁路需要关闭，问在保证首都到其余所有城市的最短路不变的条件下，最多有多少条铁路是不需要的。

首先我们可以跑一遍单源最短路（最好dij，spfa的用优先队列卡过去）。然后我们枚举火车线路，如果端点的最短路径大于火车线路，那么肯定要删除。如果端点的最短路径等于火车线路，且最短路径条数大于1，那么也要删除。

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f
#define maxn 100010
using namespace std;
typedef long long ll;
typedef pair<long,int> pii;
template <class T>
inline void read(T &res){
    char c;res=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9'){
        res=res*10+(c-'0');
        c=getchar();
    }
}
///////
struct edge{
    int to;
    ll cost;
    edge(){}
    edge(int _to,ll _cost):to(_to),cost(_cost) {}
};
int n,m,k;
vector<edge>e[maxn];
ll dis[maxn];
int qaq[maxn];
edge train[maxn];
int vis[maxn],from[maxn];
void dijkstra(int st){
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(from,0,sizeof(0));
    priority_queue< pii,vector< pii >,greater< pii > > que;
    que.push(make_pair(0,1));
    dis[st]=0;
    while(!que.empty()){
        pii now=que.top();que.pop();
        int x=now.second;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=0;i<e[x].size();i++){
            int Next=e[x][i].to;int len=e[x][i].cost;
            if(dis[x]+len<dis[Next]){
                dis[Next]=dis[x]+len;
                from[Next]=1;
                que.push(make_pair(dis[Next],Next));
            }
            else if(dis[x]+len==dis[Next]) from[Next]++;
        }
    }
}
int ans;
int main()
{
        read(n);read(m);read(k);
        for(int i=1;i<=m;i++){
            int u,v,len;
            scanf("%d %d %d",&u,&v,&len);
            e[u].push_back(edge(v,len));
            e[v].push_back(edge(u,len));
        }
        int cnt=1;
        for(int i=1;i<=k;i++){
            int v,len;scanf("%d %d",&v,&len);
            if(qaq[v]<=len&&qaq[v]) {ans++;continue;}
            e[1].push_back(edge(v,len));
            qaq[v]=len;
            train[cnt++]=edge(v,len);
        }
        dijkstra(1);
        for(int i=1;i<cnt;i++){
            if(dis[train[i].to]<train[i].cost) ans++;
            else if(dis[train[i].to]==train[i].cost&&from[train[i].to]>1){
                from[train[i].to]--;
                ans++;
            }
        }
        printf("%d\n",ans);
}

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define maxn 100010

using namespace std;

typedef long long ll;

typedef pair<long,int> pii;

template <class T>

inline void read(T &res){

char c;res=0;

while((c=getchar())<'0'||c>'9');

while(c>='0'&&c<='9'){

res=res*10+(c-'0');

c=getchar();

}

///////

struct edge{

int to;

ll cost;

edge(){}

edge(int _to,ll _cost):to(_to),cost(_cost) {}

};

int n,m,k;

vector<edge>e[maxn];

ll dis[maxn];

int qaq[maxn];

edge train[maxn];

int vis[maxn],from[maxn];

void dijkstra(int st){

memset(dis,inf,sizeof(dis));

memset(vis,0,sizeof(vis));

memset(from,0,sizeof(0));

priority_queue< pii,vector< pii >,greater< pii > > que;

que.push(make_pair(0,1));

dis[st]=0;

while(!que.empty()){

pii now=que.top();que.pop();

int x=now.second;

if(vis[x]) continue;

vis[x]=1;

for(int i=0;i<e[x].size();i++){

int Next=e[x][i].to;int len=e[x][i].cost;

if(dis[x]+len<dis[Next]){

dis[Next]=dis[x]+len;

from[Next]=1;

que.push(make_pair(dis[Next],Next));

}

else if(dis[x]+len==dis[Next]) from[Next]++;

}

int ans;

int main()

{

read(n);read(m);read(k);

for(int i=1;i<=m;i++){

int u,v,len;

scanf("%d %d %d",&u,&v,&len);

e[u].push_back(edge(v,len));

e[v].push_back(edge(u,len));

}

int cnt=1;

for(int i=1;i<=k;i++){

int v,len;scanf("%d %d",&v,&len);

if(qaq[v]<=len&&qaq[v]) {ans++;continue;}

e[1].push_back(edge(v,len));

qaq[v]=len;

train[cnt++]=edge(v,len);

}

dijkstra(1);

for(int i=1;i<cnt;i++){

if(dis[train[i].to]<train[i].cost) ans++;

else if(dis[train[i].to]==train[i].cost&&from[train[i].to]>1){

from[train[i].to]--;

ans++;

}

printf("%d\n",ans);

}

451E.Devu and Flowers（组合数学）

题意：有n个盒子，从这n个盒子中选s支花（有的盒子可以不选），每个花坛有f[i]支花，同一个花坛的花颜色相同，不同花坛的花颜色不同，问说可以有多少种方案数。

如果没有f[i]的限制，那么题目相当于问 $x_1+x_2+...+x_n=s,x_i\geq 0$ 的方案数。那么很明显由隔板法得到方案数为 $\binom{s+n-1}{n-1}$ 。对于这个题目很明显这个答案会包括超过某些f[i]的答案。发现n才20，所以我们可以枚举一下超过的花坛有哪些组合，然后用容斥原理算出答案。注意如果某次超出的花坛为i，那么相当于把 $x_1+x_2+...+x_n=s,x_i\geq 0$ 这个式子右边的s减去一个f[i]+1再做插板法。因为模数很大，而项数很小，所以不用lucas，直接循环算出组合数即可。

#include <bits/stdc++.h>
#define mod 1000000007
#define maxn 23
using namespace std;
typedef long long ll;

ll n,s;
ll quick_pow(ll a,ll k)
{
    ll res=1LL;
    while(k){
        if(k&1) res=(res*a)%mod;
        k>>=1;
        a=(a*a)%mod;
    }
    return res;
}
ll C(ll n,ll m)
{
    if(n<m) return 0;
    ll dis=max(n-m,m);
    ll cnt=min(n-m,m);
	ll fact1=1LL,fact2=1LL;
	for(int i=1;i<=cnt;i++)
	{
		fact1=fact1*(((ll)i+dis)%mod)%mod;fact2=fact2%mod*(ll)i%mod;
	}
    ll res=(fact1%mod*quick_pow(fact2,mod-2)%mod)%mod;
    return res;
}
ll f[maxn];
int main()
{
    scanf("%I64d %I64d",&n,&s);
    for(int i=0;i<n;i++) scanf("%I64d",&f[i]);
    int maxx=((1<<n)-1);
    ll ans=0;
    for(int i=0;i<=maxx;i++){
        ll sum=0;int flag=1;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                flag=-flag;
                sum+=(f[j]+1LL);
            }
        }
        if(sum>s) continue;
        ans=(ans+flag*C(s-sum+n-1,n-1)+mod)%mod;
    }
    printf("%I64d\n",ans);
}

#include <bits/stdc++.h>

#define mod 1000000007

#define maxn 23

using namespace std;

typedef long long ll;

ll n,s;

ll quick_pow(ll a,ll k)

{

ll res=1LL;

while(k){

if(k&1) res=(res*a)%mod;

k>>=1;

a=(a*a)%mod;

}

return res;

}

ll C(ll n,ll m)

{

if(n<m) return 0;

ll dis=max(n-m,m);

ll cnt=min(n-m,m);

ll fact1=1LL,fact2=1LL;

for(int i=1;i<=cnt;i++)

{

fact1=fact1*(((ll)i+dis)%mod)%mod;fact2=fact2%mod*(ll)i%mod;

}

ll res=(fact1%mod*quick_pow(fact2,mod-2)%mod)%mod;

return res;

}

ll f[maxn];

int main()

{

scanf("%I64d %I64d",&n,&s);

for(int i=0;i<n;i++) scanf("%I64d",&f[i]);

int maxx=((1<<n)-1);

ll ans=0;

for(int i=0;i<=maxx;i++){

ll sum=0;int flag=1;

for(int j=0;j<n;j++){

if(i&(1<<j)){

flag=-flag;

sum+=(f[j]+1LL);

}

if(sum>s) continue;

ans=(ans+flag*C(s-sum+n-1,n-1)+mod)%mod;

}

printf("%I64d\n",ans);

}

382A. Ksenia and Pan Scales

给出两个字符串S和T。S串中以’|’为分隔符，分成两部分。问你是否可以通过把T全部分成两部分（可以为空）分别给S中的两部分，让他们长度变得相同。

字符串模拟一下，用substr实在是方便。

#include <bits/stdc++.h>

using namespace std;
string s,t;
int main()
{
    cin>>s>>t;
    int len1=s.length();int len2=t.length();
    int p=0;
    for(int i=0;i<len1;i++){
        if(s[i]=='|')
            p=i;
    }
    int q=len1-1-p;
    string a=s.substr(0,p);
    string b;
    if(p==len1-1) b="";
    else b=s.substr(p+1,len1);
    if(p==q){
        if(len2%2) {puts("Impossible");return 0;}
        else {
            int pp=len2/2;
            cout<<a<<t.substr(0,pp)<<"|"<<b<<t.substr(pp,len2)<<endl;
        }
    }
    else {
        if((len2+len1-1)%2||p>len2+q||p+len2<q) {puts("Impossible");return 0;}
        else{
            int len=(len1-1+len2)/2;
            cout<<a<<t.substr(0,len-p)<<"|"<<b<<t.substr(len-p,len2)<<endl;
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

string s,t;

int main()

{

cin>>s>>t;

int len1=s.length();int len2=t.length();

int p=0;

for(int i=0;i<len1;i++){

if(s[i]=='|')

p=i;

}

int q=len1-1-p;

string a=s.substr(0,p);

string b;

if(p==len1-1) b="";

else b=s.substr(p+1,len1);

if(p==q){

if(len2%2) {puts("Impossible");return 0;}

else {

int pp=len2/2;

cout<<a<<t.substr(0,pp)<<"|"<<b<<t.substr(pp,len2)<<endl;

}

else {

if((len2+len1-1)%2||p>len2+q||p+len2<q) {puts("Impossible");return 0;}

else{

int len=(len1-1+len2)/2;

cout<<a<<t.substr(0,len-p)<<"|"<<b<<t.substr(len-p,len2)<<endl;

}

543B. Destroying Roads

给出N个点和M条边，每条边的边权为1。给出S1,T1,len1,S2,T2,len2.问现在最多删去多少条边，可以让S1到T1的距离不超过len1，从S2到T2的距离不超过len2。

$N \leq 3000$ , $1\leq M \leq min(3000,n*(n-1)/2)$

思路：把问题转化成至少有多少条边才可以满足让S1到T1的距离不超过len1，从S2到T2的距离不超过len2。假设我们找到了S1到T1的最短距离为dis1，S2到T2的最短距离为dis2。假设这两段最短路之间没有公共部分，那答案就是dis1+dis2。如果两段路径中间有重叠部分的话，我们可以通过枚举来得到答案。通过bfs暴力预处理出每个点对之间的最短距离，枚举就是O(1)的了。

#include <bits/stdc++.h>
#define maxn 3333
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;

int n,m,s1,t1,len1,s2,t2,len2;
int dis[maxn][maxn];
int vis[maxn];
vector<int>e[maxn];
void bfs(int st){
    memset(vis,0,sizeof(vis));
    queue<int>que;vis[st]=1;que.push(st);dis[st][st]=0;
    while(!que.empty()){
        int now=que.front();que.pop();
        int Size=e[now].size();
        vis[now]=1;
        for(int i=0;i<Size;++i){
            if(vis[e[now][i]]) continue;
            if(dis[st][e[now][i]]>dis[st][now]+1) dis[st][e[now][i]]=dis[st][now]+1;
            que.push(e[now][i]);
        }
    }
}
int main()
{
    memset(dis,inf,sizeof(dis));
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;scanf("%d %d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    scanf("%d %d %d",&s1,&t1,&len1);
    scanf("%d %d %d",&s2,&t2,&len2);
    for(int i=1;i<=n;i++) bfs(i);
    if(dis[s1][t1]>len1||dis[s2][t2]>len2) {puts("-1");return 0;}
    int ans=dis[s1][t1]+dis[s2][t2];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dis[s1][i]+dis[i][j]+dis[j][t1]<=len1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=len2)
                ans=min(ans,dis[s1][i]+dis[i][j]+dis[j][t1]+dis[s2][i]+dis[j][t2]);
            if(dis[s1][j]+dis[i][j]+dis[i][t1]<=len1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=len2)
                ans=min(ans,dis[s1][j]+dis[i][j]+dis[i][t1]+dis[s2][i]+dis[j][t2]);
        }
    }
    printf("%d\n",m-ans);
}

#include <bits/stdc++.h>

#define maxn 3333

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

int n,m,s1,t1,len1,s2,t2,len2;

int dis[maxn][maxn];

int vis[maxn];

vector<int>e[maxn];

void bfs(int st){

memset(vis,0,sizeof(vis));

queue<int>que;vis[st]=1;que.push(st);dis[st][st]=0;

while(!que.empty()){

int now=que.front();que.pop();

int Size=e[now].size();

vis[now]=1;

for(int i=0;i<Size;++i){

if(vis[e[now][i]]) continue;

if(dis[st][e[now][i]]>dis[st][now]+1) dis[st][e[now][i]]=dis[st][now]+1;

que.push(e[now][i]);

}

int main()

{

memset(dis,inf,sizeof(dis));

scanf("%d %d",&n,&m);

for(int i=1;i<=m;i++){

int u,v;scanf("%d %d",&u,&v);

e[u].push_back(v);

e[v].push_back(u);

}

scanf("%d %d %d",&s1,&t1,&len1);

scanf("%d %d %d",&s2,&t2,&len2);

for(int i=1;i<=n;i++) bfs(i);

if(dis[s1][t1]>len1||dis[s2][t2]>len2) {puts("-1");return 0;}

int ans=dis[s1][t1]+dis[s2][t2];

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

if(dis[s1][i]+dis[i][j]+dis[j][t1]<=len1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=len2)

ans=min(ans,dis[s1][i]+dis[i][j]+dis[j][t1]+dis[s2][i]+dis[j][t2]);

if(dis[s1][j]+dis[i][j]+dis[i][t1]<=len1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=len2)

ans=min(ans,dis[s1][j]+dis[i][j]+dis[i][t1]+dis[s2][i]+dis[j][t2]);

}

printf("%d\n",m-ans);

}

623A. Graph and String

题意：给出一个n（n<=500）个结点的无向图，每个结点标号”abc”三个字母其中一个。将标号为相同字母的结点连边，将所有标号为b的结点与其它标号的结点连边。给出图的m个连边，求一种合法的标号方案，不存在输出’NO’。

一个b标号的点肯定是和其余点都相连的，我们先把这样的点标上b。然后枚举剩余的点以及他们的相连情况，假设我们枚举到了的还没标号的点都标上’a’，那么和它相连的没标号的就一定是’a’，不相邻的一定是c。这样就可以判断出来了。我最后又判断一下每个点的度。不知道有没有必要。。。反正判一下没什么错吧。。。

#include <bits/stdc++.h>
#define maxn 555
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m;
int e[maxn][maxn];
int du[maxn],color[maxn];
int a,b,c;
int main()
{
    memset(color,-1,sizeof(color));
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i) {
        int u,v;scanf("%d %d",&u,&v);
        e[u][v]=e[v][u]=1;
        du[u]++;du[v]++;
    }
    a=0,b=0,c=0;
    for(int i=1;i<=n;++i) if(du[i]==n-1) {color[i]=1;b++;}
    for(int i=1;i<=n;++i){
        if(color[i]==1) continue;
        if(color[i]==-1) {color[i]=0;a++;}
        for(int j=1;j<=n;++j){
            if(color[j]==1||j==i) continue;
            if(!e[i][j]&&color[j]==-1) {color[j]=2-color[i];b++;}
            else if(e[i][j]&&color[j]==-1) {color[j]=color[i];a++;}
            else{
                if(color[j]==color[i]&&(!e[i][j])) {puts("No");return 0;}
                if(color[j]!=color[i]&&(e[i][j])) {puts("No");return 0;}
            }
        }
    }
    if(a+b+c!=n) {puts("No");return 0;}
    bool flag=1;
    for(int i=1;i<=n;++i){
        if(color[i]==2)
            if(du[i]!=b+c-1) {flag=0;break;}
        if(color[i]==1)
            if(du[i]!=b+a-1) {flag=0;break;}
    }
    if(!flag) puts("No");
    else{
        puts("Yes");
        for(int i=1;i<=n;++i){
            if(color[i]==2) printf("%c",'c');
            if(color[i]==1)  printf("%c",'b');
            if(color[i]==0) printf("%c",'a');
        }
        puts("");
    }

}

#include <bits/stdc++.h>

#define maxn 555

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

int n,m;

int e[maxn][maxn];

int du[maxn],color[maxn];

int a,b,c;

int main()

{

memset(color,-1,sizeof(color));

scanf("%d %d",&n,&m);

for(int i=1;i<=m;++i) {

int u,v;scanf("%d %d",&u,&v);

e[u][v]=e[v][u]=1;

du[u]++;du[v]++;

}

a=0,b=0,c=0;

for(int i=1;i<=n;++i) if(du[i]==n-1) {color[i]=1;b++;}

for(int i=1;i<=n;++i){

if(color[i]==1) continue;

if(color[i]==-1) {color[i]=0;a++;}

for(int j=1;j<=n;++j){

if(color[j]==1||j==i) continue;

if(!e[i][j]&&color[j]==-1) {color[j]=2-color[i];b++;}

else if(e[i][j]&&color[j]==-1) {color[j]=color[i];a++;}

else{

if(color[j]==color[i]&&(!e[i][j])) {puts("No");return 0;}

if(color[j]!=color[i]&&(e[i][j])) {puts("No");return 0;}

}

if(a+b+c!=n) {puts("No");return 0;}

bool flag=1;

for(int i=1;i<=n;++i){

if(color[i]==2)

if(du[i]!=b+c-1) {flag=0;break;}

if(color[i]==1)

if(du[i]!=b+a-1) {flag=0;break;}

}

if(!flag) puts("No");

else{

puts("Yes");

for(int i=1;i<=n;++i){

if(color[i]==2) printf("%c",'c');

if(color[i]==1) printf("%c",'b');

if(color[i]==0) printf("%c",'a');

}

puts("");

}

650A. Watchmen

给定二维平面的n个坐标，求满足 $| x i - x j | + | y i - y j | = \sqrt{(x i - x j) * (x i - x j) + (y i - y j) * (y i - y j)}$ 的点对数

$1 \leq n \leq 10^{5}, 1 \leq x_{i}, y_{i} \leq 10^{9}$

发现曼哈顿距离等于欧几里得距离，在二维平面上只有两点的x或者y相同才可能。所以用个map记录一下即可。但是因为有重点的存在，两个重点会被多算一次(x和y各一次)。所以再开个map记录一下点的个数即可。

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
pii c[maxn];
int n;
map<int,int>x,y;
map<pii,int>cnt;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d %d",&c[i].first,&c[i].second);
    ll ans=0;
    for(int i=1;i<=n;++i){
        ans+=x[c[i].first];ans+=y[c[i].second];
        x[c[i].first]++;y[c[i].second]++;
        ans-=cnt[c[i]];
        cnt[c[i]]++;
    }
    printf("%I64d\n",ans);

}

#include <bits/stdc++.h>

#define maxn 200010

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

pii c[maxn];

int n;

map<int,int>x,y;

map<pii,int>cnt;

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;++i) scanf("%d %d",&c[i].first,&c[i].second);

ll ans=0;

for(int i=1;i<=n;++i){

ans+=x[c[i].first];ans+=y[c[i].second];

x[c[i].first]++;y[c[i].second]++;

ans-=cnt[c[i]];

cnt[c[i]]++;

}

printf("%I64d\n",ans);

}

460C. Number of Ways

题意：给你n个数，让你要把序列分成连续的三部分，要求每一部分的和相等。n<=1e5

预处理前缀和，然后扫一遍前缀和，开一个数组记录每个i之前（包括i在内）有多少个前缀和为sum/3的。然后倒着扫一遍后缀和，发现一个为sum/3的后缀和的时候，我们需要知道在i-2的位置及之前有多少个前缀和为sum/3的。因为要保证每一部分都不为空。

#include <bits/stdc++.h>
#define maxn 500010
using namespace std;
typedef long long ll;
int n,a[maxn];
int cnt[maxn];
ll sum;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    if(sum%3) {puts("0");return 0;}
    ll tmp=0,num=0;
    for(int i=1;i<=n-1;i++){
        tmp+=a[i];
        if(tmp==sum/3) num++;
        cnt[i]=num;
    }
    ll ans=0;tmp=0;
    for(int i=n;i>=3;i--){
        tmp+=a[i];
        if(tmp==sum/3) ans+=cnt[i-2];
    }
    printf("%I64d\n",ans);
}

#include <bits/stdc++.h>

#define maxn 500010

using namespace std;

typedef long long ll;

int n,a[maxn];

int cnt[maxn];

ll sum;

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;++i){

scanf("%d",&a[i]);

sum+=a[i];

}

if(sum%3) {puts("0");return 0;}

ll tmp=0,num=0;

for(int i=1;i<=n-1;i++){

tmp+=a[i];

if(tmp==sum/3) num++;

cnt[i]=num;

}

ll ans=0;tmp=0;

for(int i=n;i>=3;i--){

tmp+=a[i];

if(tmp==sum/3) ans+=cnt[i-2];

}

printf("%I64d\n",ans);

}

229C. Triangles

POI原题啊，考虑反面就可以了。。。

#include <bits/stdc++.h>
#define maxn 1000100
using namespace std;
typedef long long ll;
ll n,m;
int du[maxn];
int main()
{
    scanf("%I64d %I64d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;scanf("%d %d",&u,&v);
        du[u]++,du[v]++;
    }
    ll tot=n*(n-1)*(n-2)/6;
    ll cnt=0;
    for(int i=1;i<=n;i++)
        cnt=cnt+(ll)du[i]*(n-1-du[i]);
    printf("%I64d\n",tot-cnt/2);
}

#include <bits/stdc++.h>

#define maxn 1000100

using namespace std;

typedef long long ll;

ll n,m;

int du[maxn];

int main()

{

scanf("%I64d %I64d",&n,&m);

for(int i=1;i<=m;i++){

int u,v;scanf("%d %d",&u,&v);

du[u]++,du[v]++;

}

ll tot=n*(n-1)*(n-2)/6;

ll cnt=0;

for(int i=1;i<=n;i++)

cnt=cnt+(ll)du[i]*(n-1-du[i]);

printf("%I64d\n",tot-cnt/2);

}

472A. Design Tutorial: Learn from Math

题意：给出一个n（ $12\leq n \leq 10^{6}$ ），让你把它分成两个合数之和。

首先这个肯定是可以的。对于奇数的话，拆成9和n-9，因为n-9一定是偶数且大于2，所以这两个一定是两个合数。对于偶数的话，拆成8和n-8，因为n-8是偶数，所以这两个一定是合数。当然这是题解的证明，我们直接预处理出素数表，暴力枚举即可。

#include <bits/stdc++.h>

using namespace std;
int prime[1000005];
bool isprime[1000005];
int numprime;
void getprime()
{
    memset(prime,0,sizeof(prime));
    memset(isprime,true,sizeof(isprime));
    isprime[1]=0,isprime[0]=1;
    for(int i=2;i<=1000000;i++){
        if(isprime[i])
            prime[numprime++]=i;
        for(int j=0;j<numprime&&prime[j]*i<=1000000;j++){
            isprime[prime[j]*i]=false;
            if(i%prime[j]==0)
                break;
        }
    }
}
int n;
int main()
{
    int i,j;
    getprime();
    scanf("%d",&n);
    for(i=4;i<=n/2+1;i++){
        j=n-i;
        if(isprime[i]||isprime[j]) continue;
        else break;
    }
    printf("%d %d\n",i,j);
}

#include <bits/stdc++.h>

using namespace std;

int prime[1000005];

bool isprime[1000005];

int numprime;

void getprime()

{

memset(prime,0,sizeof(prime));

memset(isprime,true,sizeof(isprime));

isprime[1]=0,isprime[0]=1;

for(int i=2;i<=1000000;i++){

if(isprime[i])

prime[numprime++]=i;

for(int j=0;j<numprime&&prime[j]*i<=1000000;j++){

isprime[prime[j]*i]=false;

if(i%prime[j]==0)

break;

}

int n;

int main()

{

int i,j;

getprime();

scanf("%d",&n);

for(i=4;i<=n/2+1;i++){

j=n-i;

if(isprime[i]||isprime[j]) continue;

else break;

}

printf("%d %d\n",i,j);

}

472B. Design Tutorial: Learn from Life

题意：在1楼有n个人准备乘坐电梯，电梯每次只能装k个人。如何安排能够使得电梯运送完所有人之后再次停回到1楼时所经过的路程最少。求出这个最小路程。 $2000\leq n,k \leq 2000$

想了个贪心，我是这么想的，从需要去楼层越高的人开始装人。其实可以这么证明，假如人数n可以整除k，从小开始还是从大开始都无所谓了，因为路程肯定确定了。但是在n不可以整除k的时候，就意味着最后有不足k人，那么这时候假如有人走最高层那肯定是比走较低层的路程大。

#include <bits/stdc++.h>
#define maxn 2005
using namespace std;
int n,k,f[maxn];
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&f[i]);
    sort(f+1,f+1+n);
    int pos=n,ans=0;
    while(pos>=k){
        ans+=2*(f[pos]-1);
        pos-=k;
    }
    if(pos) ans+=2*(f[pos]-1);
    printf("%d\n",ans);
}

#include <bits/stdc++.h>

#define maxn 2005

using namespace std;

int n,k,f[maxn];

int main()

{

scanf("%d %d",&n,&k);

for(int i=1;i<=n;i++) scanf("%d",&f[i]);

sort(f+1,f+1+n);

int pos=n,ans=0;

while(pos>=k){

ans+=2*(f[pos]-1);

pos-=k;

}

if(pos) ans+=2*(f[pos]-1);

printf("%d\n",ans);

}

472C. Design Tutorial: Make It Nondeterministic

题意：省略吧。。。。

我们按照题目给出的排列，来进行判断是否这个排列可行即可。贪心的扫一遍。

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
int n;
string f[maxn],s[maxn];
int p[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>f[i]>>s[i];
    for(int i=1;i<=n;i++) cin>>p[i];
    string now=min(f[p[1]],s[p[1]]);bool flag=1;
    for(int i=2;i<=n;i++){
        if(f[p[i]]>now&&s[p[i]]>now) now=min(f[p[i]],s[p[i]]);
        else {
            if(f[p[i]]<now&&s[p[i]]<now) {flag=0;break;}
            else if(f[p[i]]<now) now=s[p[i]];
            else now=f[p[i]];
        }
    }
    if(flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

#include <bits/stdc++.h>

#define maxn 100010

using namespace std;

int n;

string f[maxn],s[maxn];

int p[maxn];

int main()

{

ios::sync_with_stdio(false);

cin>>n;

for(int i=1;i<=n;i++) cin>>f[i]>>s[i];

for(int i=1;i<=n;i++) cin>>p[i];

string now=min(f[p[1]],s[p[1]]);bool flag=1;

for(int i=2;i<=n;i++){

if(f[p[i]]>now&&s[p[i]]>now) now=min(f[p[i]],s[p[i]]);

else {

if(f[p[i]]<now&&s[p[i]]<now) {flag=0;break;}

else if(f[p[i]]<now) now=s[p[i]];

else now=f[p[i]];

}

if(flag) cout<<"YES"<<endl;

else cout<<"NO"<<endl;

}

472D. Design Tutorial: Inverse the Problem

题意：给出一个n*n的矩阵(n<=2000)，问你这个矩阵是否可能是一棵树的邻接矩阵。

额，一开始想的思路是把这个邻接矩阵求一个MST，这个MST就是那棵树了。然后再一一验证每对点之间的距离是否与邻接矩阵相同。但是这样的话可能需要一个LCA。。。不想写。。。后来问问韩司机，告诉我O(n^2)求一个MST就可以了。

我们先特判掉不符合邻接矩阵的情况，然后接下来对于每个点，都找到与它相邻最近的点为前驱，其实这就相当于求最小生成树的过程了。前驱也就相当于这棵树上的父亲，那么找到一个点u和他的前躯v后，我们再扫一下其余各点，这时候前驱v和该节点u到剩下的点的距离情况就两种了：dis[u]>dis[v]或者dis[u]<dis[v]，而两者之间的差值一定是那条边的长度，否则就不合法。

时间复杂度O(n^2)。

#include <bits/stdc++.h>
#define maxn 2005
using namespace std;
int n;
int a[maxn][maxn];
int main()
{
    scanf("%d",&n);int flag=1;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((j==i&&a[i][j]!=0)||(j!=i&&a[i][j]==0)||a[i][j]!=a[j][i]) {
                flag=0;break;
            }
    if(!flag) {puts("NO");return 0;}
    for(int i=2;i<=n;i++){
        int pre=1;
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            if(a[pre][i]>a[j][i]) pre=j;
        }
        for(int j=1;j<=n;j++){
            if(i==j||j==pre) continue;
            if(abs(a[pre][j]-a[i][j])!=a[i][pre]) flag=0;
        }
        if(!flag) break;
    }
    if(flag) puts("YES");
    else puts("NO");
}

#include <bits/stdc++.h>

#define maxn 2005

using namespace std;

int n;

int a[maxn][maxn];

int main()

{

scanf("%d",&n);int flag=1;

for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

if((j==i&&a[i][j]!=0)||(j!=i&&a[i][j]==0)||a[i][j]!=a[j][i]) {

flag=0;break;

}

if(!flag) {puts("NO");return 0;}

for(int i=2;i<=n;i++){

int pre=1;

for(int j=1;j<=n;j++){

if(i==j) continue;

if(a[pre][i]>a[j][i]) pre=j;

}

for(int j=1;j<=n;j++){

if(i==j||j==pre) continue;

if(abs(a[pre][j]-a[i][j])!=a[i][pre]) flag=0;

}

if(!flag) break;

}

if(flag) puts("YES");

else puts("NO");

}

611C. New Year and Domino

题意：给出一个h*w（h,w均小于500）的字符矩阵，每次询问一个子矩阵，问其中可以放下一个1*2的骨牌的方案数。’#’不可以放置骨牌。

考虑维护二维前缀和，这样的话每次查询的时候可以在O(h+w)的时间内得到答案。计算的时候按照容斥就可以了。但是需要注意边界上的’.’可能需要减去一些方案。发现二维前缀和比较好的计算方法就是，先处理好第一行和第一列，然后容斥的计算剩余的部分。

#include <bits/stdc++.h>

using namespace std;
int h,w,q;
char ma[555][555];
int sum[555][555];
int main()
{
    scanf("%d %d",&h,&w);getchar();
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++)
            scanf("%c",&ma[i][j]);
        getchar();
    }
    for(int i=1;i<=h;i++) {
        if(ma[i][1]=='.'&&ma[i-1][1]=='.') sum[i][1]=sum[i-1][1]+1;
        else sum[i][1]=sum[i-1][1];
    }
    for(int i=1;i<=w;i++) {
        if(ma[1][i]=='.'&&ma[1][i-1]=='.') sum[1][i]=sum[1][i-1]+1;
        else sum[1][i]=sum[1][i-1];
    }
    for(int i=2;i<=h;i++){
        for(int j=2;j<=w;j++){
            if(ma[i][j]=='.'&&ma[i-1][j]=='.') sum[i][j]+=1;
            if(ma[i][j]=='.'&&ma[i][j-1]=='.') sum[i][j]+=1;
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    scanf("%d",&q);
    while(q--){
        int r1,c1,r2,c2;scanf("%d %d %d %d",&r1,&c1,&r2,&c2);
        int ans=sum[r2][c2]-sum[r1-1][c2]-sum[r2][c1-1]+sum[r1-1][c1-1];
        for(int i=r1;i<=r2;i++)
            if(ma[i][c1]=='.'&&ma[i][c1-1]=='.') ans--;
        for(int i=c1;i<=c2;i++)
            if(ma[r1][i]=='.'&&ma[r1-1][i]=='.') ans--;
        printf("%d\n",ans);
    }
}

#include <bits/stdc++.h>

using namespace std;

int h,w,q;

char ma[555][555];

int sum[555][555];

int main()

{

scanf("%d %d",&h,&w);getchar();

for(int i=1;i<=h;i++){

for(int j=1;j<=w;j++)

scanf("%c",&ma[i][j]);

getchar();

}

for(int i=1;i<=h;i++) {

if(ma[i][1]=='.'&&ma[i-1][1]=='.') sum[i][1]=sum[i-1][1]+1;

else sum[i][1]=sum[i-1][1];

}

for(int i=1;i<=w;i++) {

if(ma[1][i]=='.'&&ma[1][i-1]=='.') sum[1][i]=sum[1][i-1]+1;

else sum[1][i]=sum[1][i-1];

}

for(int i=2;i<=h;i++){

for(int j=2;j<=w;j++){

if(ma[i][j]=='.'&&ma[i-1][j]=='.') sum[i][j]+=1;

if(ma[i][j]=='.'&&ma[i][j-1]=='.') sum[i][j]+=1;

sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];

}

scanf("%d",&q);

while(q--){

int r1,c1,r2,c2;scanf("%d %d %d %d",&r1,&c1,&r2,&c2);

int ans=sum[r2][c2]-sum[r1-1][c2]-sum[r2][c1-1]+sum[r1-1][c1-1];

for(int i=r1;i<=r2;i++)

if(ma[i][c1]=='.'&&ma[i][c1-1]=='.') ans--;

for(int i=c1;i<=c2;i++)

if(ma[r1][i]=='.'&&ma[r1-1][i]=='.') ans--;

printf("%d\n",ans);

}

4C. Registration system

哈希加上map计数。。。水题

#include <bits/stdc++.h>
#define maxn 100010
#define inf 0x3f3f3f3f
#define mod1 1000000007
#define mod2 998244353
#define H 233
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n;
map<pii,int>ma;
int get_hash(char s[],int mod){
    ll res=0;int len=strlen(s+1);
    for(int i=1;i<=len;i++)
        res=(res*H%mod+s[i])%mod;
    return res;
}
char s[35];
int main()
{
    scanf("%d",&n);
    while(n--){
        scanf(" %s",s+1);
        pii res=make_pair(get_hash(s,mod1),get_hash(s,mod2));
        if(ma[res]) printf("%s%d\n",s+1,ma[res]);
        else puts("OK");
        ma[res]++;
    }
}

#include <bits/stdc++.h>

#define maxn 100010

#define inf 0x3f3f3f3f

#define mod1 1000000007

#define mod2 998244353

#define H 233

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

int n;

map<pii,int>ma;

int get_hash(char s[],int mod){

ll res=0;int len=strlen(s+1);

for(int i=1;i<=len;i++)

res=(res*H%mod+s[i])%mod;

return res;

}

char s[35];

int main()

{

scanf("%d",&n);

while(n--){

scanf(" %s",s+1);

pii res=make_pair(get_hash(s,mod1),get_hash(s,mod2));

if(ma[res]) printf("%s%d\n",s+1,ma[res]);

else puts("OK");

ma[res]++;

}

732D. Exams

二分答案，然后贪心验证。贪心的思路是，每个考试科目肯定是越晚考越好，这样可以有更多的时间复习。所以保存下来每科的最晚考试时间，然后扫一遍，看每门是否可以在规定的最晚时间内完成即可。

#include <bits/stdc++.h>
#define maxn 100010
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,vis[maxn],a[maxn],d[maxn];
int day[maxn],last[maxn];
bool check(int mid){
    int cnt=0;
    for(int i=mid;i;i--){
        if(d[i]==0||vis[d[i]]==mid) continue;
        vis[d[i]]=mid;
        day[++cnt]=d[i];
        last[d[i]]=i;
    }
    if(cnt!=m) return 0;
    ll pos=0;
    for(int i=m;i;i--){
        if(pos+a[day[i]]<last[day[i]]) pos+=a[day[i]]+1LL;
        else return 0;
    }
    return 1;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    for(int j=1;j<=m;j++) scanf("%d",&a[j]);
    int L=1,R=n,ans=-1;
    while(L<=R){
        int mid=((L+R)>>1);
        if(check(mid)){
            ans=mid;
            R=mid-1;
        }
        else L=mid+1;
    }
    printf("%d\n",ans);
}

#include <bits/stdc++.h>

#define maxn 100010

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

int n,m,vis[maxn],a[maxn],d[maxn];

int day[maxn],last[maxn];

bool check(int mid){

int cnt=0;

for(int i=mid;i;i--){

if(d[i]==0||vis[d[i]]==mid) continue;

vis[d[i]]=mid;

day[++cnt]=d[i];

last[d[i]]=i;

}

if(cnt!=m) return 0;

ll pos=0;

for(int i=m;i;i--){

if(pos+a[day[i]]<last[day[i]]) pos+=a[day[i]]+1LL;

else return 0;

}

return 1;

}

int main()

{

scanf("%d %d",&n,&m);

for(int i=1;i<=n;i++) scanf("%d",&d[i]);

for(int j=1;j<=m;j++) scanf("%d",&a[j]);

int L=1,R=n,ans=-1;

while(L<=R){

int mid=((L+R)>>1);

if(check(mid)){

ans=mid;

R=mid-1;

}

else L=mid+1;

}

printf("%d\n",ans);

}

732E. Sockets

题意：略。

用map贪心乱搞了一通。因为s不超过1e9，所以每个电源最多被适配器操作31次就会变成0了。那么我们可以每个电源，按照从小到大的顺序，不断操作。当在computer里找到匹配的就标记一下。这样从小到大的顺序可以保证适配器数目最小。因为对于同一个可以被匹配的电脑，小的电源会先匹配上。

#include <bits/stdc++.h>
#define maxn 200010
#define inf 0x3f3f3f3f
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
int n,m,ptos[maxn],cnt[maxn];
pii p[maxn],s[maxn];
map<pii,int>ma;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%d",&p[i].first);
        p[i].second=i;
        ma[p[i]]=-1;
    }
    sort(p+1,p+1+n);
    for(int i=1;i<=m;i++) {
        scanf("%d",&s[i].first);
        s[i].second=i;
    }
    sort(s+1,s+1+m);
    int ans1=0,ans2=0;
    for(int i=1;i<=m;i++){
        int tmp=s[i].first;
        for(int j=0;j<=31;j++){
            int pos=lower_bound(p+1,p+1+n,mp(tmp,0))-p;
            if(pos!=n+1&&p[pos].first==tmp&&ma[p[pos]]==-1){
                ans1++;ans2+=j;
                ma[p[pos]]=i;
                ptos[p[pos].second]=s[i].second;
                p[pos].second=-1;
                cnt[s[i].second]=j;
                break;
            }
            tmp=ceil(1.0*tmp/2.0);
        }
    }
    cout<<ans1<<" "<<ans2<<endl;
    for(int i=1;i<=m;i++){
        if(i!=1) printf(" ");
        printf("%d",cnt[i]);
    }
    puts("");
    for(int i=1;i<=n;i++) {
        if(i!=1) printf(" ");
        printf("%d",ptos[i]);
    }
    puts("");
}

#include <bits/stdc++.h>

#define maxn 200010

#define inf 0x3f3f3f3f

#define mp make_pair

using namespace std;

typedef long long ll;

typedef pair<int,int>pii;

int n,m,ptos[maxn],cnt[maxn];

pii p[maxn],s[maxn];

map<pii,int>ma;

int main()

{

scanf("%d %d",&n,&m);

for(int i=1;i<=n;i++) {

scanf("%d",&p[i].first);

p[i].second=i;

ma[p[i]]=-1;

}

sort(p+1,p+1+n);

for(int i=1;i<=m;i++) {

scanf("%d",&s[i].first);

s[i].second=i;

}

sort(s+1,s+1+m);

int ans1=0,ans2=0;

for(int i=1;i<=m;i++){

int tmp=s[i].first;

for(int j=0;j<=31;j++){

int pos=lower_bound(p+1,p+1+n,mp(tmp,0))-p;

if(pos!=n+1&&p[pos].first==tmp&&ma[p[pos]]==-1){

ans1++;ans2+=j;

ma[p[pos]]=i;

ptos[p[pos].second]=s[i].second;

p[pos].second=-1;

cnt[s[i].second]=j;

break;

}

tmp=ceil(1.0*tmp/2.0);

}

cout<<ans1<<" "<<ans2<<endl;

for(int i=1;i<=m;i++){

if(i!=1) printf(" ");

printf("%d",cnt[i]);

}

puts("");

for(int i=1;i<=n;i++) {

if(i!=1) printf(" ");

printf("%d",ptos[i]);

}

puts("");

}

732A. Buy a Shovel

随便搞搞。。。

#include <bits/stdc++.h>

using namespace std;
int k,r;
int main()
{
    scanf("%d %d",&k,&r);
    int i,tmp=k;
    if(k%10==r||k%10==0) {puts("1");return 0;}
    for(i=2;i<=10;i++){
        tmp+=k;
        if(tmp%10==r||tmp%10==0) break;
    }
    cout<<i<<endl;
}

#include <bits/stdc++.h>

using namespace std;

int k,r;

int main()

{

scanf("%d %d",&k,&r);

int i,tmp=k;

if(k%10==r||k%10==0) {puts("1");return 0;}

for(i=2;i<=10;i++){

tmp+=k;

if(tmp%10==r||tmp%10==0) break;

}

cout<<i<<endl;

}

732B. Cormen — The Best Friend Of a Man

根据题模拟一下。如果出现少于k次的话，尽量放到第二天了，算是一个贪心？

#include <bits/stdc++.h>
#define REP(i,x,y) for(int i=x;i<(y);i++)
using namespace std;
int n,k;
int a[555];
int main()
{
    scanf("%d %d",&n,&k);
    REP(i,1,n+1) scanf("%d",&a[i]);
    if(n==1) {
        printf("%d\n%d\n",0,a[1]);
        return 0;
    }
    int ans=0;
    REP(i,2,n){
        if(a[i-1]+a[i]<k){
            ans+=k-a[i-1]-a[i];
            a[i]+=k-a[i-1]-a[i];
        }
    }
    if(a[n-1]+a[n]<k) {
        ans+=k-a[n]-a[n-1];
        a[n]+=k-a[n]-a[n-1];
    }
    printf("%d\n",ans);
    REP(i,1,n+1){
        if(i!=1) printf(" ");
        printf("%d",a[i]);
    }
    puts("");
}

#include <bits/stdc++.h>

#define REP(i,x,y) for(int i=x;i<(y);i++)

using namespace std;

int n,k;

int a[555];

int main()

{

scanf("%d %d",&n,&k);

REP(i,1,n+1) scanf("%d",&a[i]);

if(n==1) {

printf("%d\n%d\n",0,a[1]);

return 0;

}

int ans=0;

REP(i,2,n){

if(a[i-1]+a[i]<k){

ans+=k-a[i-1]-a[i];

a[i]+=k-a[i-1]-a[i];

}

if(a[n-1]+a[n]<k) {

ans+=k-a[n]-a[n-1];

a[n]+=k-a[n]-a[n-1];

}

printf("%d\n",ans);

REP(i,1,n+1){

if(i!=1) printf(" ");

printf("%d",a[i]);

}

puts("");

}

732C. Sanatorium

题意：给出b,d,s分别代表吃了多少天的早饭，中饭和晚饭。你可能忘记吃了一些次的饭，现在需要求出最少可能忘记吃了多少次饭。

首先需要确定一个天数，找出吃了最多次数的饭，那么减去1就是最少过了这么多天。然后和剩下的两个比比，就可以求出答案。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll a[5];
int main()
{
    scanf("%I64d %I64d %I64d",&a[1],&a[2],&a[3]);
    sort(a+1,a+4);
    ll maxx=a[3]-1;
    ll ans=(maxx>=a[1] ? maxx-a[1] : 0);
    ans+=(maxx>=a[2] ? maxx-a[2] : 0);
    printf("%I64d\n",ans);
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[5];

int main()

{

scanf("%I64d %I64d %I64d",&a[1],&a[2],&a[3]);

sort(a+1,a+4);

ll maxx=a[3]-1;

ll ans=(maxx>=a[1] ? maxx-a[1] : 0);

ans+=(maxx>=a[2] ? maxx-a[2] : 0);

printf("%I64d\n",ans);

}

732F. Tourist Reform

题意：给出n个点m条边的一个无向图。保证没有重边。现在对每一条边定向，每个节点都可以有一个值r。代表这个点可以从i到达多少个点。现在需要求出让最少的r值最大的分配方案。

把所有的边双联通分量求出来，那么就形成了一个个连通块，连通块之间有桥边。那么在各个连通块内，我们dfs走出来环就可以给这个连通块内的各个边定向。而且因为是在连通分量内，所以这些边的定向是无所谓的。现在考虑桥边如何定向。其实想一想，把所有连通块缩点后只保留桥边，那么就形成了一个无根树。那么最后剩下来的最小的r一定是在某一个连通块内。这个连通块的桥边都是指向他的没有出边。也就是根节点。那么最大的最少r应该正是最大的连通块中点的个数。其余别的连通块的桥边均指向这个根就可以了。

#include <bits/stdc++.h>
#define maxn 400050
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,dfs_clock;
struct edge{
    int u,v,flag,id;
    edge(int _u,int _v,int _f,int i):u(_u),v(_v),flag(_f),id(i){}
};
vector<int>e[maxn];
vector<edge>edges;
void add_edge(int u,int v,int i){
    edges.push_back(edge(u,v,0,i));
    edges.push_back(edge(v,u,0,i));
    int cnt=edges.size();
    e[u].push_back(cnt-2);e[v].push_back(cnt-1);
}
int pre[maxn],low[maxn];
void dfs_bcc(int u,int fa){
    pre[u]=low[u]=(++dfs_clock);
    int Size=e[u].size();
    for(int i=0;i<Size;i++){
        int Next=e[u][i];
        int v=edges[Next].v;
        if(v==fa) continue;
        if(!pre[v]){
            dfs_bcc(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>pre[u])
                edges[Next].flag=edges[Next^1].flag=1;
        }
        else if(pre[v]<pre[u]) low[u]=min(low[u],pre[v]);
    }
}
int vis[maxn],col,cnt[maxn],cnt2[maxn];
pii ans[maxn];
void dfs(int u,int fa,int col){
    vis[u]=col;int Size=e[u].size();
    for(int i=0;i<Size;i++){
        int Next=e[u][i];
        int v=edges[Next].v;
        if(v==fa||edges[Next].flag) continue;
        ans[edges[Next].id]=make_pair(u,v);
        edges[Next].flag=edges[Next^1].flag=2;
        if(vis[v]==col) continue;
        dfs(v,u,col);
    }
}
int vis2[maxn];
void bfs(int st){
    queue<int>que;
    que.push(st);vis2[st]=1;
    while(!que.empty()){
        int now=que.front();que.pop();
        int Size=e[now].size();
        for(int i=0;i<Size;i++){
            int Next=e[now][i];
            int v=edges[Next].v;
            if(vis2[v]) continue;
            if(edges[Next].flag==1)
                ans[edges[Next].id]=make_pair(v,now);
            vis2[v]=1;
            que.push(v);
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;scanf("%d %d",&u,&v);
        add_edge(u,v,i);
    }
    dfs_clock=0;
    dfs_bcc(1,0);
    for(int i=1;i<=n;i++)
        if(!vis[i]) col++,dfs(i,0,col);
    int maxx=0,pos=-1;
    for(int i=1;i<=n;i++)
        cnt[vis[i]]++;
    for(int i=1;i<=n;i++){
        if(maxx<cnt[vis[i]]){
            maxx=cnt[vis[i]];
            pos=i;
        }
    }
    printf("%d\n",maxx);
    bfs(pos);
    for(int i=1;i<=m;i++)
        printf("%d %d\n",ans[i].first,ans[i].second);

}

#include <bits/stdc++.h>

#define maxn 400050

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

int n,m,dfs_clock;

struct edge{

int u,v,flag,id;

edge(int _u,int _v,int _f,int i):u(_u),v(_v),flag(_f),id(i){}

};

vector<int>e[maxn];

vector<edge>edges;

void add_edge(int u,int v,int i){

edges.push_back(edge(u,v,0,i));

edges.push_back(edge(v,u,0,i));

int cnt=edges.size();

e[u].push_back(cnt-2);e[v].push_back(cnt-1);

}

int pre[maxn],low[maxn];

void dfs_bcc(int u,int fa){

pre[u]=low[u]=(++dfs_clock);

int Size=e[u].size();

for(int i=0;i<Size;i++){

int Next=e[u][i];

int v=edges[Next].v;

if(v==fa) continue;

if(!pre[v]){

dfs_bcc(v,u);

low[u]=min(low[u],low[v]);

if(low[v]>pre[u])

edges[Next].flag=edges[Next^1].flag=1;

}

else if(pre[v]<pre[u]) low[u]=min(low[u],pre[v]);

}

int vis[maxn],col,cnt[maxn],cnt2[maxn];

pii ans[maxn];

void dfs(int u,int fa,int col){

vis[u]=col;int Size=e[u].size();

for(int i=0;i<Size;i++){

int Next=e[u][i];

int v=edges[Next].v;

if(v==fa||edges[Next].flag) continue;

ans[edges[Next].id]=make_pair(u,v);

edges[Next].flag=edges[Next^1].flag=2;

if(vis[v]==col) continue;

dfs(v,u,col);

}

int vis2[maxn];

void bfs(int st){

queue<int>que;

que.push(st);vis2[st]=1;

while(!que.empty()){

int now=que.front();que.pop();

int Size=e[now].size();

for(int i=0;i<Size;i++){

int Next=e[now][i];

int v=edges[Next].v;

if(vis2[v]) continue;

if(edges[Next].flag==1)

ans[edges[Next].id]=make_pair(v,now);

vis2[v]=1;

que.push(v);

}

int main()

{

scanf("%d %d",&n,&m);

for(int i=1;i<=m;i++){

int u,v;scanf("%d %d",&u,&v);

add_edge(u,v,i);

}

dfs_clock=0;

dfs_bcc(1,0);

for(int i=1;i<=n;i++)

if(!vis[i]) col++,dfs(i,0,col);

int maxx=0,pos=-1;

for(int i=1;i<=n;i++)

cnt[vis[i]]++;

for(int i=1;i<=n;i++){

if(maxx<cnt[vis[i]]){

maxx=cnt[vis[i]];

pos=i;

}

printf("%d\n",maxx);

bfs(pos);

for(int i=1;i<=m;i++)

printf("%d %d\n",ans[i].first,ans[i].second);

}

酷狗的小窝

曾经的acmer

Codeforces题目泛做计划

427B.Prison Transfer

475B.Strongly Connected City

510C.Fox And Names

437C.The Child and Toy

500A.New Year Transportation

519B. A and B and Compilation Errors（模拟）

639B. Bear and Forgotten Tree 3（构造乱搞）

298A. Snow Footprints（模拟+分类讨论）

298B. Sail（模拟+贪心）

382C. Arithmetic Progression（分类讨论）

450D. Jzzhu and Cities（最短路）

451E.Devu and Flowers（组合数学）

382A. Ksenia and Pan Scales

543B. Destroying Roads

623A. Graph and String

650A. Watchmen

460C. Number of Ways

229C. Triangles

472A. Design Tutorial: Learn from Math

472B. Design Tutorial: Learn from Life

472C. Design Tutorial: Make It Nondeterministic

472D. Design Tutorial: Inverse the Problem

611C. New Year and Domino

4C. Registration system

732D. Exams

732E. Sockets

732A. Buy a Shovel

732B. Cormen — The Best Friend Of a Man

732C. Sanatorium

732F. Tourist Reform

发表评论取消回复

427B.Prison Transfer

475B.Strongly Connected City

510C.Fox And Names

437C.The Child and Toy

500A.New Year Transportation

519B. A and B and Compilation Errors（模拟）

639B. Bear and Forgotten Tree 3（构造乱搞）

298A. Snow Footprints（模拟+分类讨论）

298B. Sail（模拟+贪心）

382C. Arithmetic Progression（分类讨论）

450D. Jzzhu and Cities（最短路）

451E.Devu and Flowers（组合数学）

382A. Ksenia and Pan Scales

543B. Destroying Roads

623A. Graph and String

650A. Watchmen

460C. Number of Ways

229C. Triangles

472A. Design Tutorial: Learn from Math

472B. Design Tutorial: Learn from Life

472C. Design Tutorial: Make It Nondeterministic

472D. Design Tutorial: Inverse the Problem

611C. New Year and Domino

4C. Registration system

732D. Exams

732E. Sockets

732A. Buy a Shovel

732B. Cormen — The Best Friend Of a Man

732C. Sanatorium

732F. Tourist Reform

发表评论 取消回复

发表评论取消回复