LDU20級新生排位賽第二場

pick一波出題人：
BD
A
CI
F
GH
J
L
剩下的沒找到鏈接55

A. UpMing的迷宮

代碼：

int n,m,ans[222222],a[2222][2222],vis[2222][2222];
int dx[4] = {1,0,-1,0},cnt,num;
int dy[4] = {0,1,0,-1};
int ok (int x,int y) {
	if(vis[x][y]||x<1||x>n||y<1||y>n) return 0;
	return 1;
}
void dfs(int x,int y) {
	vis[x][y] =cnt ;
	num++;
	for(int i=0 ; i<4 ; i++) {
		int x1 = x+dx[i];
		int y1 = y+dy[i];
		if(ok(x1,y1)==0) continue;
		if(a[x][y]==a[x1][y1]) continue;
		dfs(x1,y1);
	}
}
int main() {
	n=read(),m=read();
	rep(i,1,n) rep(j,1,n) scanf("%1d",&a[i][j]);
	rep(i,1,n) rep(j,1,n) if(vis[i][j]==0) ++cnt,dfs(i,j),ans[cnt]=num,num=0;
	for(int i=1 ; i<=m ; i++) {
		int x = read();
		int y = read();
		printf("%d\n",ans[vis[x][y]]);
	}

	return 0;
}

B. SEQUEL_Road

題目出處

思路：

按照完全二分圖的情況匹配是最優的（不會證明），姑且當做規律題，

當n為偶數時，平均分配的時候是上面n/2個點，下面n/2個點，所以是n/2*n/2

當n為奇數時，一邊為n/2個點，另一邊是n-n/2個點，乘積就是答案，

代碼：

int main(){
    int n;
    while(~scanf("%d",&n)){
        int x=n/2;
        printf("%d\n",x*(n-x));
    }
    return 0;
}

C. 寶可夢

題目出處

只是改了改題目背景，不知道為什么沒人過，題解網上有很多，種類并查集or帶權并查集都可，

D. 多娜多娜一起來坐高鐵

題目出處

E. 唐人街探案

簽到題

F. 恐怖的咬手鯊魚

wyb學長說是個逆尼姆博弈的板子題，然而博弈論一點也沒有講，

傳送門

G. 歡歡的簽到題

upd:題解
費馬小定理求逆元

參考

H. 歡歡的快速冪

出題人說是個歐拉定理，我不會所以就等到明天再更新~
upd:題解 把異或改成了和

I. 真的簽到題

線段樹區間修改區間求和，注意懶惰標記的優先級，

由于乘法的運算級高于加法，要保證在加法之前，將乘法進行完畢，

也就是說在修改時，要先將乘法的懶標下傳，再將加法的懶標下傳，

附上我11個月前寫的lj代碼：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
int n,m,w[maxn],p;
struct node{
    int l,r;
    ll sum,add,mul;//維護區間和和懶惰標記
}a[maxn*4];
void pushup(int u){
    a[u].sum=(a[u<<1].sum+a[u<<1|1].sum)%p;
}
void qdown(node &t,int add,int mul){
    t.sum=((ll)t.sum*mul+(ll)(t.r-t.l+1)*add)%p;
    t.mul=(ll)t.mul*mul%p;
    t.add=((ll)t.add*mul+add)%p;///也要考慮乘積的懶惰標記產生的影響
}
void pushdown(int u){
    qdown(a[u<<1],a[u].add,a[u].mul);
    qdown(a[u<<1|1],a[u].add,a[u].mul);
    a[u].add=0;a[u].mul=1;///注意乘積的懶惰標記傳遞后應當為1
}
void build(int u,int l,int r){
    if(l==r) a[u]={l,r,w[r],0,1};
    else{
        a[u]={l,r,0,0,1};
        int mid=l+r >> 1;
        build(u<<1,l,mid);build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void update(int u,int l,int r,int add,int mul){
    if(a[u].l>=l&&a[u].r<=r) qdown(a[u],add,mul);
    else{
        pushdown(u);
        int mid=a[u].l+a[u].r >>1;
        if(l<=mid) update(u<<1,l,r,add,mul);
        if(r>mid) update(u<<1|1,l,r,add,mul);
        pushup(u);
    }
}
int qask(int u,int l,int r){
    if(a[u].l>=l&&a[u].r<=r) return a[u].sum;
    pushdown(u);
    int mid=a[u].l+a[u].r >>1;
    int sum=0;
    if(l<=mid) sum=qask(u<<1,l,r);
    if(r>mid) sum=(sum+qask(u<<1|1,l,r))%p;
    return sum;
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    build(1,1,n);
    while(m--){
        int op,l,r,v;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1){
            scanf("%d",&v);
            update(1,l,r,0,v);
        }
        else if(op==2){
            scanf("%d",&v);
            update(1,l,r,v,1);
        }
        else printf("%d\n",qask(1,l,r));
    }
    return 0;
}

J. 學呀學呀學矩形

唯一分解定理
代碼;

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=9999991;
const int MAXM=50000+10;
const int MAXN=1000000+10;
ll p[MAXN], c[MAXN], cnt;
ll qpow(ll n, ll m)
{
    ll ans = 1;
    while(m)
	{
        if(m & 1) ans = ans*n% mod;
        n = n*n%mod;
        m >>= 1;
    }
    return ans%mod;
}
void deal(ll a)
{
    for(int i=2;i<=a;i ++)
	{
        if(a % i == 0)
		{
            p[cnt++] = i;
            while(a % i == 0)
			{
                a /= i;
                c[i] ++;
            }
        }
    }
}

int main()
{
	int a,b;
	cin>>a>>b;
    deal(a);
    ll ans = 1;
    for(int i=0;i<cnt;i++)
        ans =(ans%mod*((qpow(p[i], b*c[p[i]]+1)-1+mod)%mod))%mod*(qpow(p[i]-1,mod-2)%mod)%mod;
    cout<<(ans+mod)%mod<<endl;
    fclose;
}

K. 小明的疑惑

這是假的簽到題吧，當時icpc模擬賽被卡了好久的題，

題解

L. 如何優雅的寫單詞

正解是kmp，資料出水了所以暴力也能過，
upd:題解
代碼：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
int n,k;
char p[107];
int net[maxn];
void kmp_next(){
    net[0]=0;
    net[1]=0;
    for(int j=1;j<n;j++){
        int k = net[j];
        while(p[j] != p[k] && k) k = net[k];
        if(p[j] == p[k]) net[j+1] = k+1;
        else net[j+1] = 0;
    }
}
int main(){
    /// freopen("1.in","r",stdin);
    /// freopen("1.out","w",stdout);
    cin >> n >> k;
    cin >> p;
    kmp_next();
    ///for(int i=1;i<=n;i++) printf("%d ",net[i]);
    ///puts("");
    cout<<p;
    for(int i=1;i<k;i++){
        for(int j=net[n];j<n;j++) printf("%c",p[j]);
    }
    return 0;
}