【NOIPシミュレーション】プチデカダンDay 1

D1T1
質問A:小奇掘削

【    】
         ，          （     w）   ，             n   。
【    】
    2 ：       。 
1.   ：     a[i]，     ，   a[i]*p   ，      k%， p=p*(1-0.01k)
2.   ：    b[i]，     ，   b[i]*p   ，      c%， p=p*(1+0.01c)（p        ）
 ：                
             

  
   4   n，k，c，w。
  n ，  2   type，x。
type 1          ，x       a[i]；
type 2          ，x      b[i]；

  
        （      ），       。

    
5 50 50 10
1 10
1 20
2 10
2 20
1 30

    
375.00

  
  30%    n<=100
  50%    n<=1000，k=100
  100%    n<=100000，0<=k，c，w，a[i]，b[i]<=100
       10^9

初眼構想:記憶化検索
しかし、運行が間違っているようで、私もなぜか分かりません.
正解:線形ダイナミックプランニング

得られたお金または支払ったお金は現在の能力に比例するため、現在の能力とお金の混合値

を格納する配列を設定することができる.

前効性があるので逆さに押すのはなぜか分かりませんが

コアコード

for(int i=n;i>=1;i--) {
        if(s[i][0]==1) f[i-1]=max(f[i],f[i]*(1-0.01*k)+a[i]*w);
        else f[i-1]=max(f[i],f[i]*(1+0.01*c)-b[i]*w);
    }

D1T2
質問B:チビの数列

【    】
                。
 【    】
       n   ，  m   ，       l，r P，   (a[l'] + a[l'+1] + ... + a[r']) mod P    。
  l <= l' <= r' <= r。 
              。

  
          n m，             。
    n   ， a[1]..a[n]。
   m ，     l，r P，      。

  
      ，               

    
4 2
8 15 9 9
1 3 10
1 4 17

    
2
1

  
  20%    n<=100，m<=100，p<=200
  40%    n<=200，m<=1000，p<=500
  70%    n<=100000，m<=10000，p<=200
  100%    n<=500000，m<=10000，p<=500，1<=a[i]<=10^9

初眼の考え方:暴力

配列記録プレフィックス和を開き、すべての区間50 pts

を列挙する.
暴力の最適化

現在値が0であることが判明すると、break 90 pts

に直接breakすることができる.

まだ1つの桶を開けることができて、具体的なやり方は私もよく分かりませんが、ACができて、走るのは正解よりずっと速いです.暴力の大法は

です.
正解:バランスツリー

は依然として配列記録接頭辞和を開き、毎回現在の前駆者を取得して最小差を探し、バランスツリーを挿入し、毎回

を初期化することを覚えている.
ACコード

#include
#include
#include
#define SI 500010
#define inf 0x3f3f3f3f
using namespace std;
struct treap {
	int l,r,dat,val;
}a[1010];
int n,m,rt,mn,tot,t[SI];
long long s[SI];
inline int New(int val) {
	a[++tot].val=val;
	a[tot].dat=rand();
	return tot;
}
inline void zig(int &p) {//   
	int q=a[p].l;
	a[p].l=a[q].r,a[q].r=p,p=q;
}
inline void zag(int &p) {//   
	int q=a[p].r;
	a[p].r=a[q].l,a[q].l=p,p=q;
}
inline void insert(int &p,int val) {
	if(p==0) {
		p=New(val);
		return;
	}
	if(val==a[p].val) return;
	if(val<a[p].val) {
		insert(a[p].l,val);
		if(a[p].dat<a[a[p].l].dat) zig(p);
	}
	else {
		insert(a[p].r,val);
		if(a[p].dat<a[a[p].r].dat) zag(p);
	}
}
inline void Remove(int &p,int val) {
	if(p==0) return;
	if(val==a[p].val) {
		mn=0;
		return;
	}
	if(val<a[p].val) Remove(a[p].l,val);
	else {
		mn=min(mn,val-a[p].val);
		Remove(a[p].r,val);
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d",&t[i]);
		s[i]=s[i-1]+t[i];
	}
	while(m--) {
		memset(a,0,sizeof(a));
		int l,r,p;
		scanf("%d%d%d",&l,&r,&p);
		int ans=p;
		if(r-l+1>=p) {
			printf("0
");
			continue;
		}
		rt=tot=0; insert(rt,0);
		for(int j=l;j<=r;j++) {
			int tmp=(s[j]-s[l-1])%p;
			mn=inf; Remove(rt,tmp);
			insert(rt,tmp);
			ans=min(ans,mn);
			if(!ans) break;
		}
		printf("%d
",ans);
	}
	return 0;
}

D1T3
奇ちゃんが地球に帰る

【    】
   ，         ，          。
 【    】
    ，      1       n   ，          。
          ，                  ，  ，   a b        b a          。
      ：“             。”
             ，         。                                  。
               ，                。

  
          ， 1   T，      。
      ，   1       n，m，              。
   m ，      i，j t，     i   j      t。 i j           。

  
     T ，        。
                 ，         ，     1   n     。（             0）。
       1    n，   -1。

    
1
4 5
1 2 1
1 3 1
2 3 -3
3 1 1
3 4 1

    
2

  
【    】
          1,         1,        1→2→3→4,     2+(-2)+2=2。
 
【    】
1，2    ，           1
3，4    ，n<=10
5，6    ，-100<=t<=100
  100%   T<=10，n<=100，m<=n*(n-1)，-100000<=t<=100000
           

初眼構想:図上二分
正解:図上二分
真・D 1唯一本当にできる問題

まず最も重要な点は、複数のデータが初期化されたことを覚えています.memsetが終わったと思ってはいけません.そして、あなたが作ったcntがゼロに戻ることを忘れないでください.私はこのように2回

を実行しました.

負のループを判断する必要があります.SPFAで反復回数を判断することができます.反復回数がnより大きいと負のループがあることがわかります.

時間を長くすることができます.

SPFAでは、中継点が目的地に到達できるかどうかを判断する必要があります.floyedアルゴリズムを使用して、2点間が

に接続されているかどうかを記録するためにブール配列を開きます.

二はそれぞれ

を間違えた.
ACコード

#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
struct edge {
    int nex,to,w;
}e[10010];
int T,n,m,cnt,ans,head[105],dis[105],Cnt[105];
bool vis[105][105],v[105]; queue<int> q;
inline int read() {
    int c=getchar(),x=0,cf=1;
    while(c<'0'||c>'9') {
        if(c=='-') cf=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*cf;
}
inline void add(int x,int y,int z) {
    e[++cnt].to=y,e[cnt].w=z,e[cnt].nex=head[x],head[x]=cnt;
}
inline bool spfa(int s,int d) {
    memset(dis,0x3f,sizeof(dis));
    memset(v,false,sizeof(v));
    memset(Cnt,0,sizeof(Cnt));
    dis[s]=0,v[s]=1,Cnt[s]=0;
    q.push(s);
    while(q.size()) {
        int x=q.front(); q.pop(); v[x]=0;
        if(Cnt[x]>=n) return true;
        for(int i=head[x];i;i=e[i].nex) {
            int y=e[i].to,z=e[i].w;
            if(dis[y]>dis[x]+z+d&&vis[y][n]) {
                dis[y]=dis[x]+z+d;
                Cnt[y]=Cnt[x]+1;
                if(Cnt[y]>=n) return true;
                if(!v[y]) q.push(y),v[y]=1;
            }
        }
    }
    if(dis[n]<0||dis[n]==inf) return true;
    return false;
}
int main() {
    T=read();
    while(T--) {
        memset(head,0,sizeof(head));
        memset(e,0,sizeof(e));
        memset(vis,false,sizeof(vis));
        n=read(),m=read(); cnt=0;
        for(int i=1;i<=m;i++) {
            int x,y,z;
            x=read(),y=read(),z=read();
            add(x,y,z); vis[x][y]=true;
        }
        for(int i=1;i<=n;i++) vis[i][i]=true;
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(vis[i][k]&&vis[k][j]) vis[i][j]=true;
        if(!vis[1][n]) {
            printf("-1
");
            continue;
        }
        int l=-100000,r=100000;
        ans=-1;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(spfa(1,mid)) l=mid+1;
            else r=mid-1,ans=dis[n];
        }
        printf("%d
",ans);
    }
    return 0;
}

最終得点100+90+0=190、まだまだ頑張らなきゃ