Codeforces Round #303 (Div. 2)

題目鏈接:http://codeforces.com/contest/545

A. Toy Cars

枚舉判斷每一個車

def solve():
    n,res=int(input()),[];
    for i in range(0,n):
        if all(s in ("0","2","-1") for s in input().split()):
            res.append(i+1);
    print(len(res));
    print(*res);

B. Equidistant String

當兩個字符串的distance為奇數是肯定不存在

def solve():
    x=input();
    y=input();
    pos=[];
    count=0;
    n=len(x);
    for i in range(n):
        if(x[i]!=y[i]):
            pos.append(i);
            count+=1;
    if(count%2==1): print("impossible");
    else:
        xx=list(x);
        for i in range(count//2):
            if(xx[pos[i]]=='0'): xx[pos[i]]='1';
            else: xx[pos[i]]='0';
        print("".join(xx));

C. Woodcutters

兩頭的樹肯定可以倒,從第二棵樹開始枚舉判斷向左倒,還是向右倒即可

def solve():
    n=int(input());
    h=[0]*n;
    x=[0]*n;
    for i in range(n):
        x[i],h[i]=map(int,input().split());
    ans=2;
    for i in range(1,n-1):
        if(x[i]-x[i-1]>h[i]): ans+=1;
        elif (x[i+1]-x[i]>h[i]):
            ans+=1;
            x[i]+=h[i];
    if(n<=2): ans=n;
    print(ans);

D. Queue

先排序,然後維護前綴和,求大於等於前綴和的最小的數字,貪心即可

const int N=100005;
int a[N];
void solve() {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    priority_queue<int, vector<int>, greater<int> > q;
    for(int i=1;i<n;i++) q.push(a[i]);
    int res=1;
    long long sum=a[0];
    while(q.size()>0) {
        if(q.top()>=sum) {
            res++;
            sum+=q.top();
        }
        q.pop();
    }
    cout<<res<<endl;
}

E. Paths and Trees

求最短路上的所有邊

const int N=300005;
typedef long long LL;
typedef pair<int,pair<LL,int> > PIP;
typedef pair<pair<LL, LL>, pair<int, int> > PPP;
vector<pair<int,pair<LL,int> > > g[N];
bool vis[N];
void solve() {
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        int u,v,c;
        cin>>u>>v>>c;
        g[u].push_back(make_pair(v,make_pair(c,i+1)));
        g[v].push_back(make_pair(u,make_pair(c,i+1)));
    }
    LL dis=0;
    int s;
    cin>>s;
    priority_queue<pair<pair<LL, LL>, pair<int, int> > > q;
    q.push(make_pair(make_pair(0,0),make_pair(s,0)));
    vector<int> res;
    while(q.size()>0) {
        PPP u=q.top();
        q.pop();
        if(vis[u.second.first]) continue;
        vis[u.second.first]=true;
        if(u.second.second>0) res.push_back(u.second.second);
        dis-=u.first.second;
        for(int i=0;i<g[u.second.first].size();i++) {
            PIP v=g[u.second.first][i];
            q.push(make_pair(make_pair(u.first.first-v.second.first,-v.second.first),make_pair(v.first,v.second.second)));
        }
    }
    cout<<dis<<endl;
    for(int i=0;i<res.size();i++) {
        cout<<res[i]<<' ';
    }
    cout<<endl;
}