NOIPシミュレーション問題

文字列string.pas/c/cpp 1S/256MB 【題名の説明】文字列を与えます.この文字列に2つの隣接する文字が同じである場合、この2つの文字を消去します.注意しなければならないのは、この2つの文字を消去すると、新しい隣接する文字が同じになる可能性があります.例えば、初期の文字列はabcddcで、ddは2つの隣接する同じ文字です.「dd」を消去すると、得られる文字列はabccであり、この場合ccはまた2つの隣接する同じ文字であるため、ccを消去すべきである.残りの列に2つの隣接する文字が存在しないまで、以上の操作を繰り返し、最終的に残りの列を出力します.また、同じ文字の複数の消去順序が答えに影響を及ぼさないことに注意してください.たとえば、初期文字列adccdeedの場合、adccdeed->addeed->aeed->aeed->adまたはadccded->adccdd->adcc->adの場合、最終的な出力結果はadです.【入力】ファイル名を入力:string.in入力の最初の行.初期文字列であり、すべての文字が小文字である文字列を含む.【出力】出力ファイル名:string.out出力は1行であり、1つの文字列を含み、複数回の消去操作を行った後に最終的に残った文字列である.【入力サンプル】adccdeed【出力サンプル】ad【データ範囲】100%のデータに対して、文字列の長さは1〜200000である.
ポインタで早く書くようですが、なぜスタックを使わないのですか.

#include
#include
#include
#include
using namespace std;
stack <char> st,ts; 
int main()
{
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout); 
    char s[200001];
    scanf("%s",s);
    for(int i=0;i<strlen(s);i++)
    {
        if(st.empty()||st.top()!=s[i]) 
        {
           st.push(s[i]);
           continue;
        }
        while(!st.empty()&&st.top()==s[i])  st.pop();
    }
    while(!st.empty()) 
    {
        ts.push(st.top());
        st.pop(); 
    }
    while(!ts.empty()) 
    {
       printf("%c",ts.top());
       ts.pop();
    }
} 

風邪ウイルスpas/c/cpp 1S/256MB 【題目説明】風邪ウイルスが学校に伝播している.この学校にはn人の学生、m人の学生サークルがあり、学生一人一人が複数のサークルに参加している可能性がある.同じサークルの学生の交流が多いため、一人の学生が風邪ウイルスに感染すれば、彼の所属するサークルのすべての学生が風邪ウイルスに感染することが知られている.現在、0番の学生が感染していることが知られている風邪のウィルス、今どれだけの人が風邪のウィルスに感染することができることを聞きます.【入力】入力ファイル:suspects.in入力の最初の行は、学生の数とサークルの数を表す2つの整数nとmであり、学生の番号は0からn-1である.次に、m行は、まず1つの数kiであり、このサークルにki人がいることを示し、次にkiの整数であり、このサークルの学生一人一人の番号aijを示す.【出力】出力ファイル:suspects.out出力は1行で、1つの整数を含む.風邪ウイルスに感染した人数を示す.【入力サンプル】1004 2 1 10 5 10 13 11 12 14 2 0 1 2 9 2【出力サンプル】7【データ範囲】100%のデータに対して、3<=n<=30000が100%のデータに対して、3<=m<=500が100%のデータに対して、1<=ki<=nが100%のデータに対して、0<=aij<=nである.
裸でコレクションを調べる

#include
#include
#include
using namespace std;
int k[50100],p[50001],fl[50001],pp,qq,ans;
int find(int x){return p[x]=(p[x]==x)? x:find(p[x]);}
void Union(int x,int y)
{
    int px=find(x);
    int py=find(y);
    p[py]=px;
}
int main()
{
    int n,m,i,j;
    cin>>n>>m;
    while(m!=0||n!=0)
    {
    ans=0;
    memset(k,0,sizeof(k));
    for(i=0;i<=n;i++) p[i]=i;
    for(i=1;i<=m;i++)
    {
       cin>>k[i]>>pp;
       for(j=2;j<=k[i];j++)
       {
          cin>>qq;
          Union(pp,qq);
       }
    }
    for(i=0;i<=n;i++) if(find(i)==find(0)) ans++;
    cout<cin>>n>>m;
    }
}

弱点だpas/c/cpp 2 S/256 MB【タイトル説明】一隊の勇士があなたに攻撃しています.勇士一人一人に戦闘値aiがあります.しかし、この勇士には致命的な弱点があります.i<=j<=kでai>aj>akとなると、彼ら全体の戦闘力に影響します.私たちはこのようなグループ(i,j,k)をこの勇士の弱点と呼びます.このチームの勇士の弱点の数をお願いします.【入力】入力ファイル:weakness.in入力の最初の行は、勇士の数を表す整数nである.次の行は、勇士の戦闘値aiを表すn個の整数を含む.【出力】入力ファイル:weakness.out出力は、整数を含む1行である.この勇士の弱点数を示す.【入力サンプル】4 10 8 3 1【出力サンプル】4【データ範囲】30%のデータに対して、3<=n<=100が100%のデータに対して、3<=n<=100,000が100%のデータに対して、1<=a=1,000,000,000がaiごとに異なる
木の配列を使うには、コンニャクはまだあまりできません.

#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n;
int t[2][1000005],a[1000005];
void add(int f,int x,int val)
{
    for(int i=x;i<=1000000;i+=i&(-i))
        t[f][i]+=val;
}
ll query(int f,int x)
{
    ll sum=0;
    for(int i=x;i;i-=i&(-i))
        sum+=t[f][i];
    return sum;
}
int main()
{
    freopen("weakness.in","r",stdin);
    freopen("weakness.out","w",stdout); 
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++)
        add(0,a[i],1);
    for(int i=1;i<=n;i++)
    {
        add(0,a[i],-1);
        ans+=(query(1,1000000)-query(1,a[i]))*query(0,a[i]-1);
        add(1,a[i],1);
    }
    printf("%I64d",ans);
    return 0;
}

スライド窓pas/c/cpp 3 S/256 MB【題名説明】n個の要素を含む配列に、長さkの窓が左から右にスライドしている.窓が一つの位置にスライドするたびに、窓にk個の要素が見える.以下の例に示すように、配列は[13-1-35 3 6]であり、kは3:に等しいと仮定する
窓位置最小値最大値[1 3-1]-3 5 3 6 7-1 3 1[3-1-3]5 3 6 7-3 3 3 1 3[-1-35]3 6 7-3 5 5 1 3-1[-3 5 3 3 3]6 7-3 5 1 3 1 3[5 3 6 6 6]7 3 6 6 1-3 5[3 6 7]3 7

            ，      k           。

【入力】入力ファイル:window.in入力の最初の行は2つの整数n,k,nが配列の長さを表し、kが窓の長さを表す.次の行はn個の整数を含み、このn個の要素の配列を表す.【出力】出力ファイル:window.out出力は2行を含み、各行はn-k+1個の整数を含み、1行目は窓が左から右にスライドする過程の最小値を表し、2行目は窓が左から右にスライドする過程の最大値を表す.【入力サンプル】8 3 1 3 1 3-1-3 3 3 3 3 3 3 3 3 3 3 5 6 7【出力サンプル】【データ範囲】100%のデータに対して、3<=n<=1000000、1<=k<=nであり、配列内の各要素はint範囲内である
単調キュー

#include
#include
#include
#include
#include
#include
using namespace std;
int n,m,i,a[1000010],f_min[1000010],f_max[1000010],p[1000010],nub[1000010],h=1,t=0;
int q[1000020],num[1000020],head=1,tail=0;

int main()
{
   q[tail]=num[tail]=0;
   cin>>n>>m;
   for(i=1;i<=n;i++)
   {
     cin>>a[i];
     while(num[head]<=i-m) head++;
     while(q[tail]>=a[i]&&tail>=head) tail--;
     q[++tail]=a[i]; 
     num[tail]=i;
     f_min[i]=q[head];
     while(nub[h]<=i-m) h++;
     while(p[t]<=a[i]&&t>=h) t--;
     p[++t]=a[i];
     nub[t]=i;
     f_max[i]=p[h];
   }
   for(i=m;i" ";
   cout<for(i=m;i" ";
   cout<return 0;
}