Codeforces 1107簡単な問題解


文書ディレクトリ
  • A題
  • B題
  • C題
  • D題
  • E題
  • F題
  • G題
  • トランスファゲート
    A題
    1つの数字をいくつかのブロックに切って、切ったk kのkの個数k≦2 kle 2 k≦2がa 1構想:シミュレーション.コード:
    #include
    #define ri register int
    using namespace std;
    typedef long long ll;
    inline int read(){
    	int ans=0;
    	char ch=getchar();
    	while(!isdigit(ch))ch=getchar();
    	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    	return ans;
    }
    int n;
    char s[500];
    int main(){
    	for(ri tt=read();tt;--tt){
    		n=read(),scanf("%s",s+1);
    		if(n==2&&s[1]>=s[2]){puts("NO");continue;}
    		puts("YES"),puts("2");
    		cout<<s[1]<<' ';
    		for(ri i=2;i<=n;++i)cout<<s[i];
    		puts("");
    	}
    	return 0;
    }
    

    B題
    トランスポートゲートの問題の簡単な説明:k番目のk kの大きい数の根がi i iの数がいくらなのかを聞くのは0≦i≦9 0le ile 9 0≦i≦9
    構想:1つの数の数本はそれに等しいm o d   9mod 9 mod 9の値.コード:
    #include
    #define ri register int
    using namespace std;
    typedef long long ll;
    inline ll read(){
    	ll ans=0;
    	char ch=getchar();
    	while(!isdigit(ch))ch=getchar();
    	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    	return ans;
    }
    const int N=400;
    int n,x;
    ll k;
    int main(){
    	for(ri tt=read();tt;--tt){
    		k=read(),x=read();
    		cout<<(k-1)*9+x<<'
    '
    ; } return 0; }

    C題
    トランスポートゲートの問題は簡単に説明します:n nのnの個数と1つの値k k kをあげて、1つの26 26の26文字のキーボードがあって、1つのキーは連続的にk kを超えることができなくて、今あなたに1つのキーのシーケンスと1回のキーに対して得ることができる重み値をあげて、最後に得られる総重み値を聞く(k k k個のa a aを押してb bを押すとk k回のa a a aを押すことができることに注意).
    構想:私たちは同じ数字のセグメントをすべて提出して、それぞれ前のk k kを大きく加算すればいいです.コード:
    #include
    #define ri register int
    using namespace std;
    typedef long long ll;
    inline int read(){
    	int ans=0;
    	char ch=getchar();
    	while(!isdigit(ch))ch=getchar();
    	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    	return ans;
    }
    const int N=2e5+5;
    int n,k,a[N];
    char s[N];
    priority_queue<int>q;
    ll ans=0;
    inline void solve(int l,int r){
    	while(!q.empty())q.pop();
    	for(ri i=l;i<=r;++i)q.push(a[i]);
    	for(ri i=1;i<=k;++i){
    		if(q.empty())break;
    		ans+=q.top(),q.pop();
    	}
    }
    int main(){
    	n=read(),k=read();
    	for(ri i=1;i<=n;++i)a[i]=read();
    	scanf("%s",s+1);
    	ans=0;
    	for(ri l=1,r=1;l<=n;l=r+1,r=l){
    		while(r<=n&&s[r]==s[r+1])++r;
    		solve(l,r);
    	}
    	cout<<ans;
    	return 0;
    }
    

    D題
    転送ドアの題意の簡単な説明:n∗n*n∗nの01 01行列a aがあって、あなたにk∗kを構築することができるかどうかを聞いて、k∣n k*kを満たして、k|n k∗kを満たして、k∣nの行列b b bを満たしてa i,j=b⌊i k⌋,⌊j k⌋a_{i,j}=b_{\lfloor{\frac ik}\rfloor,\lfloor{\frac jk}\rfloor} ai,j​=b⌊ki​⌋,⌊kj​⌋​
    構想:暴力列挙i i i、接頭辞と最適化c h e c k check checkを利用すればコードができる:
    #include
    #define ri register int
    using namespace std;
    typedef long long ll;
    inline int read(){
    	int ans=0;
    	char ch=getchar();
    	while(!isdigit(ch))ch=getchar();
    	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    	return ans;
    }
    const int N=5205;
    int n,sum[N][N];
    char s[N];
    int main(){
    	n=read();
    	for(ri i=1;i<=n;++i){
    		scanf("%s",s+1);
    		for(ri j=1,v;j<=n;j+=4){
    			if(s[(j+3)/4]>='A'&&s[(j+3)/4]<='Z')v=s[(j+3)/4]-'A'+10;
    			else v=s[(j+3)/4]-'0';
    			sum[i][j]=(v>>3)&1;
    			sum[i][j+1]=(v>>2)&1;
    			sum[i][j+2]=(v>>1)&1;
    			sum[i][j+3]=v&1;
    		}
    	}
    	for(ri i=1;i<=n;++i)for(ri j=1;j<=n;++j)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
    	for(ri i=n;i;--i){
    		if(n!=n/i*i)continue;
    		bool f=1;
    		for(ri x=1;x*i<=n;++x){
    			for(ri y=1,v;y*i<=n;++y){
    				v=sum[i*x][i*y]-sum[i*x][i*(y-1)]-sum[i*(x-1)][i*y]+sum[i*(x-1)][i*(y-1)];
    				f&=v==0||v==i*i;
    			}
    		}
    		if(f)return cout<<i,0;
    	}
    	return 0;
    }
    

    E題
    転送ゲートの題意の簡単な説明:01列を与えて、毎回連続の1段を消去することを選択することができて、貢献はa l e n,l e n a_です{len},len alen,lenは消去長さを表し,a i a_i aiは、シリアル全体を消去する最大の貢献を与えます.
    構想:先d p dp出真・a i a_i ai(a i a_i aiとa j+a i−j a_j+a_{i−j}aj+ai−jのどちらが大きいかを考慮し、後者が大きいと前者を更新する).そして、d p dp,fl,r f_を区間することができる{l,r}fl,rは区間[l,r][l,r][l,r][l,r]の寄与を表し,g l,r,k,0/1 g_{l,r,k,0/1}gl,r,k,0/1は区間[l,r][l,r][l,r]を表し,k k個の連続する0/1 0/1 0/1の最大寄与のみが残され,列挙遷移すればよい.コード:
    #include
    #define ri register int
    using namespace std;
    inline int read(){
    	int ans=0;
    	char ch=getchar();
    	while(!isdigit(ch))ch=getchar();
    	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    	return ans;
    }
    typedef long long ll;
    const int N=105;
    int n,a[N],sum[N][N];
    ll f[N],g[N][N][2];
    char s[N];
    inline void update(ll&a,ll b){a=b>a?b:a;}
    int main(){
    	memset(g,-0x3f,sizeof(g));
    	n=read(),scanf("%s",s+1);
    	for(ri i=1;i<=n;++i){
    		a[i]=f[i]=read();
    		for(ri j=1;j<i;++j)f[i]=max(f[i],f[j]+f[i-j]);
    	}
    	int cnt0=0,cnt1=0;
    	for(ri i=1;i<=n;++i)sum[1][i]=sum[1][i-1]+(s[i]=='1'),g[i][i][s[i]-'0']=f[1];
    	for(ri l=1;l<=n;++l)for(ri r=l;r<=n;++r)sum[l][r]=sum[1][r]-sum[1][l-1];
    	for(ri len=2;len<=n;++len){
    		for(ri l=1,r=l+len-1;r<=n;++l,++r){
    			if(s[l+1]=='0')update(g[l][r][0],g[l+1][r][0]+f[r-l+1-sum[l][r]]-f[r-l-sum[l][r]]);
    			if(s[r-1]=='0')update(g[l][r][0],g[l][r-1][0]+f[r-l+1-sum[l][r]]-f[r-l-sum[l][r]]);			
    			if(s[l+1]=='1')update(g[l][r][1],g[l+1][r][1]+f[sum[l][r]]-f[sum[l][r]-1]);
    			if(s[r-1]=='1')update(g[l][r][1],g[l][r-1][1]+f[sum[l][r]]-f[sum[l][r]-1]);
    			for(ri k=l;k<r;++k){
    				update(g[l][r][0],g[l][k][0]+g[k+1][r][0]);
    				update(g[l][r][0],g[l][k][0]+g[k+1][r][1]);
    				update(g[l][r][0],g[l][k][1]+g[k+1][r][0]);
    				update(g[l][r][1],g[l][k][0]+g[k+1][r][1]);
    				update(g[l][r][1],g[l][k][1]+g[k+1][r][0]);
    				update(g[l][r][1],g[l][k][1]+g[k+1][r][1]);
    			}
    		}
    	}
    	cout<<max(g[1][n][0],g[1][n][1]);
    	return 0;
    }
    

    F題
    転送ドアの問題の簡単な説明:n n nの銀行があって、あなたは毎月初めにその中の1つのローンa i aから選択することができますi ai、そして次はk i k_i kiヶ月(今月を含む)毎月末にb i bを返します.i bi元は、すべてのローン案のうち任意の1ヶ月の総現額の最大値を聞く.
    考え方:明らかに費用の流れのやり方があり、費用を利用して事前に計算すればいい.しかし、貪欲にb i b_に従うこともできます.i biは大きいから小さいまで並べ替えて、それからf i f_i fiは、合計貸付i i iヶ月の最大値がO(n 2)O(n^2)O(n 2)のd p dp dpを走ることを示している.コード:
    #include
    #define ri register int
    using namespace std;
    inline int read(){
    	int ans=0;
    	char ch=getchar();
    	while(!isdigit(ch))ch=getchar();
    	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    	return ans;
    }
    typedef long long ll;
    const int N=1005,M=250005;
    int n;
    struct Node{int a,b,c;}a[N];
    ll ans=0,f[N];
    inline void update(ll&a,const ll&b){a=b>a?b:a;}
    inline bool cmp(const Node&a,const Node&b){return a.b>b.b;}
    int main(){
    	n=read();
    	for(ri i=1;i<=n;++i)a[i].a=read(),a[i].b=read(),a[i].c=read();
    	sort(a+1,a+n+1,cmp);
    	for(ri i=1;i<=n;++i){
    		for(ri j=n-1;~j;--j){
    			update(f[j+1],f[j]+a[i].a-(ll)j*a[i].b);
    			update(f[j],f[j]+a[i].a-(ll)a[i].c*a[i].b);
    		}
    	}
    	for(ri i=0;i<=n;++i)update(ans,f[i]);
    	cout<<ans;
    	return 0;
    

    G題
    転送ゲートの問題の簡単な説明:n,a,c i,d i n,a,c_を与えるi,d_i n,a,ci,di,その中から[l,r][l,r][l,r][l,r]を選択し,寄与はa∗(r−l+1)−Σi=l r c i−m a x i=l r−1(d i+1−d i)2 a*(r−l+1)−sum_{i=l}^rc_i-max_{i=l}^{r−1}(d_{i+1}−d_i)^2 a∗(r−l+1)−Σi=lr ci−maxi=lr−1(di+1−di)2は、d d d単増を保証する.
    考え方:d p dp,f i f_を考えるi fiは、i i i iで終わるシーケンスの長さが少なくとも2 2 2 2の答えを表す.従って、i i−i−d i−1≦d j−d j−d j−d j−d−1 d_となるように、i i iから前に1番目のj j j j j jを見つけることができることは明らかである.i-d{i-1}\le d_j-d_{j−1}di−di−1≦dj−dj−1のようなf i f_i fiは、f j f_j fjと[j,i][j,i][j,i]の間の最大接尾辞と遷移ので,二分またはセグメントツリーでj j j jを求め,f i f_を更新するi fiでいいです.コード:
    #include
    #define ri register int
    using namespace std;
    inline int read(){
    	int ans=0;
    	char ch=getchar();
    	while(!isdigit(ch))ch=getchar();
    	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    	return ans;
    }
    typedef long long ll;
    const int N=3e5+5;
    int n;
    ll ans=0,f[N],sum[N],a,c[N],d[N];
    inline void update(ll&a,const ll&b){a=b>a?b:a;}
    namespace SGT{
    	#define lc (p<<1)
    	#define rc (p<<1|1)
    	#define mid (l+r>>1)
    	ll mx[N<<2];
    	inline void pushup(int p){mx[p]=max(mx[lc],mx[rc]);}
    	inline void build(int p,int l,int r){
    		mx[p]=-1;
    		if(l==r)return;
    		build(lc,l,mid),build(rc,mid+1,r),pushup(p);
    	}
    	inline int query(int p,int l,int r,ll v){
    		if(mx[p]<v)return -1;
    		if(l==r)return l;
    		return mx[rc]>=v?query(rc,mid+1,r,v):query(lc,l,mid,v);
    	}
    	inline void update(int p,int l,int r,int k,ll v){
    		if(l==r){mx[p]=v;return;}
    		k<=mid?update(lc,l,mid,k,v):update(rc,mid+1,r,k,v);
    		pushup(p);
    	}
    	#undef mid
    	#undef lc
    	#undef rc
    }
    namespace sgt{
    	#define lc (p<<1)
    	#define rc (p<<1|1)
    	#define mid (T[p].l+T[p].r>>1)
    	struct Node{int l,r;ll rs,sum;}T[N<<2];
    	inline Node operator+(const Node&a,const Node&b){return (Node){a.l,b.r,max(b.rs,b.sum+a.rs),a.sum+b.sum};}
    	inline void build(int p,int l,int r){
    		T[p].l=l,T[p].r=r;
    		if(l==r){T[p].rs=T[p].sum=a-c[l];return;}
    		build(lc,l,mid),build(rc,mid+1,r),T[p]=T[lc]+T[rc];
    	}
    	inline Node query(int p,int ql,int qr){
    		if(ql<=T[p].l&&T[p].r<=qr)return T[p];
    		if(qr<=mid)return query(lc,ql,qr);
    		if(ql>mid)return query(rc,ql,qr);
    		return query(lc,ql,mid)+query(rc,mid+1,qr);
    	}
    	#undef mid
    	#undef lc
    	#undef rc
    }
    inline ll solve(int l,int r){return sgt::query(1,l,r-1).rs+a-c[r]-(d[r]-d[r-1])*(d[r]-d[r-1]);}
    int main(){
    	n=read(),a=read(),SGT::build(1,1,n);
    	for(ri i=1;i<=n;++i)d[i]=read(),c[i]=read(),update(ans,a-c[i]),sum[i]=sum[i-1]+a-c[i];
    	sgt::build(1,1,n);
    	for(ri i=1;i<=n;++i){
    		f[i]=-1e18;
    		if(i==1)continue;
    		int pos=SGT::query(1,1,n,d[i]-d[i-1]);
    		if(pos==-1)pos=1;
    		f[i]=max(solve(pos,i),f[pos]+sum[i]-sum[pos]);
    		update(ans,f[i]),SGT::update(1,1,n,i,d[i]-d[i-1]);
    	}
    	cout<<ans;
    	return 0;
    }