latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年11月14日 星期六

[ codeforces ] 2015 German Collegiate Programming Contest (GCPC 15) + POI 10-T3 Problem M. Sums

題目:
http://codeforces.com/gym/100753

解法:
這是POI的題目,困難度很高,主要想法是使用最短路徑
設a[i]=集合中第i個元素
則d[x]=最小的K滿足 (K-x)整除於a[0],0<=x<a[0]
可以用dijkstra得到d陣列
用SPFA則會有TLE的風險
最後詢問Q是否d[Q%a[0]]<=Q,如果滿足條件表示Q可以由集合內的數字組成

code:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
int INF=2000000000,s[5005],d[50005];
set<pair<int,int > > st;
int t,n,a;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%d",&s[i]);
    for(int i=0;i<s[0];++i)d[i]=INF;
    d[0]=0;
    st.insert(make_pair(d[0],0));
    while(!st.empty()){
        pair<int,int> top=*st.begin();
        st.erase(top);
        int v=top.second;
        int x=top.first;
        for(int i=1;i<n;++i){
            int x2=x+s[i];
            int v2=(v+s[i])%s[0];
            if(x2<d[v2]){
                if(d[v2]<INF)st.erase(make_pair(d[v2],v2));
                d[v2]=x2;
                st.insert(make_pair(d[v2],v2));
            }
        }
    }
    scanf("%d",&m);
    while(m--){
        scanf("%d",&a);
        if(d[a%s[0]]<=a)printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}

沒有留言:

張貼留言