第1週のまとめ

内容概要

は、アルゴリズム

に関する

題数

関連アルゴリズム

欲張り、シミュレーション、(優先キュー、set)

HDU6299 Balanced Sequence

HDU6301 Distinct Values

HDU6308 Time Zone

内容の概要
アルゴリズムに関する
シミュレーション
問題数
1
相関アルゴリズム
欲張り、シミュレーション、(優先キュー、set)
HDU6299 Balanced Sequence
原題リンク
題意:n個の‘(’,’)’のみを含む文字列に、これらの文字列をどのように組み合わせることで、最長のバランスのとれたサブシーケンス(連続する必要がない)の長さを得ることができるかを尋ねる
思考過程と関連解法:まず各列の合法的な括弧マッチング数を統計してから、その不合法な個数を記録することができ、この時のシーケンス形式は「...」))((((((...)フォーマットで、各シーケンスに対して1つの秩序対(a,b)を処理することができ、aはこのシーケンスの左端の右括弧を代表し、bはこのシーケンスの右端の左括弧を代表する.その後、すべてのシーケンスをソートし、計算結果をシミュレートします.
ソートの貪欲さは参照コードを証明するものではありません
参照コード:

#include 
#include  
#include 
using namespace std;
const int MAXS =  100005;
struct node{
    int l,r,cnt;
    bool operator < (node const& b) const{
        if (l < r && b.l >= b.r ) return true; //a        b         a      
        if (l >= r && b.l < b.r) return false;
        //         a,b                                      
        if (l < r && b.l < b.r) return l < b.l;    
        if (l >= r && b.l >= b.r) return r > b.r;  
    }
}a[MAXS];
char s[MAXS];
int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        int n;
        scanf("%d",&n);
        for (int i = 1; i <= n; ++i){
            scanf("%s",s);
            int len = strlen(s);
            a[i].l = a[i].r = a[i].cnt = 0;
            //                                            
            for (int j = 0;j < len; ++j){
                if (s[j] == '(') a[i].r++;  //               
                else{
                    if (a[i].r > 0) {
                        a[i].r--; a[i].cnt++;
                    }else a[i].l++;
                }
            }

        }
        sort(a+1,a+n+1);
        int ans = 0;
        int lcnt = 0;
        //           
        for (int i = 1; i <= n; ++i){
            if (a[i].l > lcnt) a[i].l = lcnt;
            ans += a[i].l + a[i].cnt;
            lcnt -= a[i].l;
            lcnt += a[i].r;
        }
        printf("%d
",ans * 2);
    }
    return 0;
}

HDU6301 Distinct Values
原題リンク
題意:1つのシーケンスに対して、m行区間がその区間内のすべての数字が異なることを示し、得られる1からnまでの辞書シーケンスの最小のシーケンスにこのシーケンスを出力する
思考過程及び関連解法:問題は、重複区間の数値記入数を処理するには、使用可能な値のシーケンスを維持しなければならないため、かつこのシーケンスを維持するには毎回最小値をとる必要があるため、優先キューまたはsetを用いてこのシーケンス処理区間を維持する際に同じ区間端点に注意し、最長の反対側に処理することを保証することを考慮することができる
参照コード:

#include 
#include 
#include 
#include  
#include 
using namespace std; 
const int MAXN = 1000005;
struct node{
    int l,r;
}a[MAXN];
int ans[MAXN];
bool cmp(node a,node b){
    if (a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}
int flag[MAXN];
priority_queue<int,vector<int>,greater<int> > que;
int main(){
    int t;
    while (scanf("%d",&t)!=EOF){
            while (t--){
                int n,m;
                scanf("%d%d",&n,&m);
                for (int i = 0;i < m; ++i){
                    scanf("%d%d",&a[i].l,&a[i].r);
                }
                sort(a,a+m,cmp);
                for (int i = 1;i <= n; ++i){
                    que.push(i);
                    ans[i] = 0;
                    flag[i] = 0;
                }
                int pos = 1,k = 0;
                for (int i = 1;i <= n; ++i){
                    //       
                    while (k < m && a[k].l == i){
                        pos = max(i,pos);
                        while (pos <= a[k].r){
                            ans[pos] = que.top();
                            flag[ans[pos]] = 1;
                            que.pop();
                            pos++;
                        }
                        k++;
                    }//          ans                     
                     //printf("*%d %d*\n",i,ans[i]);
                    if (ans[i] == 0) ans[i] = 1;
                    else if (flag[ans[i]] == 1){
                        que.push(ans[i]);
                        flag[ans[i]] = 0;
                    }
                }
                for (int i = 1;i <= n; ++i){
                    printf("%d%c",ans[i],i == n ? '
' : ' ');
                } 
                while (!que.empty()) que.pop();

        }
    }

    return 0;
} 

/*set         
set<int> s;
for (int i = 1;i <= n; ++i) pre[i] = i,s.insert(i);
for (int i = 1;i <= m; ++i){scanf("%d%d",&l,&r); pre[r] = min(pre[r],l);} 
//        pre[i]        
for (int i = n-1; i >= 1; ++i) pre[i] = min(pre[i],pre[i+1]);
int cnt = 1;
for (int i = 1;i <= n; ++i){
    while (cnt < pre[i]){
    //           set       ( cnt                  )
        s.insert(ans[cnt]);
        cnt++;
    }
    ans[i] = *s.begin();
    s.erase(ans[i]);
}
*/

HDU6308 Time Zone
原題リンク
标题:タイムゾーン変換北京地区のタイムゾーン時間を対応するタイムゾーンに変換する時間
思考過程と関連解法:直接シミュレーションすればよく、時間を最小精度(分)計算に統一し、1日24*60 minの型取りに注意する.タイムゾーンは小数点でもよいので、ここで杜教のコードを見るのは不便かもしれませんが、sscanfの使い方を勉強すると、文字列をあるビットから必要なデータ型で読み出すことになります.(データ型で読み取り長を宣言可能)
参照コード:

#include 
#include 
#include 
#include  
#include 
using namespace std; 
const int MAXN = 1000005;
int _;
int sgn,a,b,ans;
double d;
char s[30]; 
int main(){
    for (scanf("%d",&_);_;_--){
        scanf("%d%d%s",&a,&b,s);
        ans = a*60+b;
        sgn = s[3] == '+' ? 1 : -1;
        sscanf(s+4,"%lf",&d);
        int c = (int)(d * 10 + 0.1);
        c = sgn * c * 6 - 8 * 60;
        ans += c;
        ans %= (24 * 60);
        if (ans < 0) ans += (24 * 60);
        printf("%02d:%02d
",ans/60,ans%60);
    }
    return 0;
}