C. Game with Chips

題意

給你一個(gè)n,m的棋盤，再給你k個(gè)棋子的坐標(biāo)，讓你移動(dòng)經(jīng)過(guò)接下來(lái)對(duì)應(yīng)的k個(gè)位置。
可以所有棋子到一個(gè)格子。
當(dāng)移動(dòng)到邊界的時(shí)候再往邊界走則原地不動(dòng)。
求所有棋子走的路線能夠滿足題意的，步數(shù)不超過(guò)2nm次。
LRUD對(duì)應(yīng)移動(dòng)的方向，輸出構(gòu)造的路徑。

思路

構(gòu)造題
當(dāng)時(shí)打的時(shí)候一直在想如何構(gòu)造最優(yōu)路徑，是BFS呢還是啥。
現(xiàn)在想想當(dāng)時(shí)真的蠢，打一個(gè)EDU第C題沒(méi)那么麻煩。
其實(shí)這道題的關(guān)鍵在于讀題，步數(shù)不超過(guò)2nm，仔細(xì)想想所有格子移動(dòng)到某個(gè)角落然后再S形遍歷全圖，這樣的步數(shù)也不可能超過(guò)2nm。

讀題很重要，注意一下數(shù)據(jù)的范圍，有利于構(gòu)造合理的算法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll n,m,k;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=2*k;i++){
		int x,y;
		cin>>x>>y;
	}
	cout<<n*(m-1)+2*n+m-3<<'\n';
	for(int i=1;i<=m-1;i++){
		cout<<'L';
	}
	for(int i=1;i<=n-1;i++){
		cout<<'U';
	}
	for(int i=1;i<=n;i++){
		if(i>1) cout<<'D';
		for(int j=1;j<=m-1;j++) cout<<((i%2==1)?'R':'L');
	}
	return 0;
}

E. Count The Blocks

題意

給你一個(gè)整數(shù)n，求 $10^n$10n內(nèi)（每個(gè)數(shù)有前導(dǎo)零）長(zhǎng)度為1到n的塊分別有多少個(gè)。塊的含義是連續(xù)相同數(shù)字的長(zhǎng)度。

思路

找規(guī)律
$f\left[n\right]=n?10^n?sum[n?1]?\left(a\right[1]?10^{n?1}+a[2]?10^{n?2}+...+a[n?1]?10^1)$f[n]=n?10n?sum[n?1]?(a[1]?10n?1+a[2]?10n?2+...+a[n?1]?101)
$sum\left[n\right]=sum[n?1]+f\left[n\right]$sum[n]=sum[n?1]+f[n]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 998244353;
const ll  maxn = 1e6 + 5;

ll ans[maxn],s[maxn],a[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	a[0]=1;
	for(int i=1;i<=n;i++) a[i]=(a[i-1]*10)%mod;
	ll res=0,k=0;
	for(int i=1;i<=n;i++){
		ans[i]=(i*a[i]-s[i-1]-k+2*mod)%mod;
		s[i]=(s[i-1]+ans[i])%mod;
		k=(k+s[i])%mod;
	}
	for(int i=n;i>=1;i--){
		cout<<ans[i]<<" ";
	}
	return 0;
}