Solution Set -「acmsguru」

首页

关于

笔记

文章

友链

Solution Set -「acmsguru」

cirnovsky / Jul 09, 2021

ACMSGURU

标红表示还没过，代码不可信任，或者咕仂。

「acmsguru - 100~109」

「acmsguru - 100」A+B

略。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll x=0,f=0; char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
signed main()
{
	printf("%d\n",read()+read());
	return 0;
}

「acmsguru - 101」Domino

显然转成图论。把有相同数字的点连边，那么问题就成了找一条路径经过且仅经过每个点一次。找出哈密顿路即可。

但是判断是 NP😭。

重建图，把数字做点，牌做边，然后就成了找欧拉路，直接来。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=200,nds=7;
signed main() {
	int n=read();
	static int a[N],b[N],deg[10],mat[10][10],ans[N],cnt,Ans[N],ANS[N],vis[10],storing[N*2],cntot;
	vector<int> id[10][10];
	for(int i=1; i<=n; ++i) a[i]=read(),b[i]=read(),++mat[++a[i]][++b[i]],++mat[b[i]][a[i]],
		++deg[a[i]],++deg[b[i]],id[a[i]][b[i]].push_back(i),storing[++cntot]=a[i],storing[++cntot]=b[i];
	int tot=0;
	for(int i=1; i<=nds; ++i) (deg[i]&1)&&(++tot);
	if(tot&&tot!=2) return puts("No solution"),0;
	std::function<void(int)> dfs=[&](int x) {
		vis[x]=1;
		for(int i=1; i<=nds; ++i) (mat[x][i])&&(--mat[x][i],--mat[i][x],dfs(i),1);
		ans[++cnt]=x;
	};
	for(int i=1; i<=nds; ++i) if(deg[i]&1) { dfs(i); break; }
	(!cnt)&&(dfs(1),1);
	for(int i=1; i<=cntot; ++i) if(!vis[storing[i]]) return puts("No solution"),0;
	for(int i=1; i<cnt; ++i) {
		if(id[ans[i]][ans[i+1]].size()) Ans[i]=id[ans[i]][ans[i+1]].back(),id[ans[i]][ans[i+1]].pop_back(),ANS[i]=0;
		else if(id[ans[i+1]][ans[i]].size()) Ans[i]=id[ans[i+1]][ans[i]].back(),id[ans[i+1]][ans[i]].pop_back(),ANS[i]=1;
	}
	for(int i=1;i<cnt;++i) printf("%d %c\n",Ans[i],ANS[i]?'-':'+');
	return 0;
}

「acmsguru - 102」Coprimes

输出 $n$ 的欧拉函数值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
signed main() {
	ll n=read(),ans=n;
	for(int i=2; i*i<=n; ++i) {
		if(n%i==0) {
			ans-=ans/i;
			for(; n%i==0; n/=i) ;
		}
	}
	if(n>1) ans-=ans/n;
	printf("%lld\n",ans);
	return 0;
}

「acmsguru - 103」Traffic Lights

暴难写的最短路板题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=400;
int n,m,st,ed,chr[2][2],a[N][N];
struct st {
	int c,t,b,p;
} lts[N];
void qwq(int v,int pr,int k) {
	if(pr<lts[v].t) {
		chr[k][0]=lts[v].c;
		chr[k][1]=lts[v].t-pr;
		return;
	}
	int tmp=(pr-lts[v].t)%(lts[v].b+lts[v].p);
	if(lts[v].c) {
		if(tmp<lts[v].b) chr[k][0]=0,chr[k][1]=lts[v].b-tmp;
		else chr[k][0]=1,chr[k][1]=lts[v].p-tmp+lts[v].b;
	}
	else {
		if(tmp<lts[v].p) chr[k][0]=1,chr[k][1]=lts[v].p-tmp;
		else chr[k][0]=0,chr[k][1]=lts[v].b-tmp+lts[v].p;
	}
}
int qaq(int v,int u,int pr,int f) {
	qwq(v,pr,0),qwq(u,pr,1);
	if(chr[0][0]==chr[1][0]) return 0;
	int tp0=chr[0][1];
	int tp1=chr[1][1];
	if(tp0==tp1) {
		if(f==2) return -1;
		else {
			int tp=qaq(v,u,pr+tp0,f+1);
			if(~tp) return tp+tp0;
			else return -1;
		}
	}
	return min(tp0,tp1);
}
int dis[N],prs[N],vis[N];
signed main() {
	st=read(),ed=read(),n=read(),m=read();
	for(int i=1; i<=n; ++i) {
		char s[10];
		scanf("%s",s);
		lts[i].c=s[0]=='P';
		lts[i].t=read();
		lts[i].b=read();
		lts[i].p=read();
	}
	const int inf=numeric_limits<int>::max();
	for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j)
		(i^j)&&(a[i][j]=inf);
	for(int i=1,x,y; i<=m; ++i) x=read(),y=read(),a[x][y]=a[y][x]=read();
	int now=st;
	for(int i=0; i<n; ++i) dis[i]=inf;
	for(int i=1; i<=n; ++i)
		(a[now][i]<inf)&&(dis[i]=a[now][i]+qaq(now,i,0,0),prs[i]=now),
		(a[now][i]==inf)&&(dis[i]=inf,prs[i]=0);
	vis[now]=1,prs[now]=0;
	for(int i=1; i<=n; ++i) {
		int k=0,m=inf;
		for(int j=1; j<=n; ++j)
			(!vis[j]&&dis[j]<m)&&(m=dis[k=j]);
		if(!k) break;
		vis[k]=1;
		for(int j=1; j<=n; ++j)
			if(k!=j&&a[k][j]!=inf) {
				int tp=qaq(k,j,dis[k],0);
				if(tp==-1) continue;
				if(dis[j]>dis[k]+tp+a[k][j]) dis[j]=dis[k]+tp+a[k][j],prs[j]=k;
			}
	}
	if(st==ed) printf("0\n%d\n",st);
	else if(dis[ed]==inf) puts("0");
	else {
		printf("%d\n",dis[ed]);
		now=ed; static int pas[N],k;
		while(prs[now]) pas[++k]=prs[now],now=prs[now];
		pas[0]=ed;
		for(int i=k; ~i; --i) printf("%d ",pas[i]);
	}
	return 0;
}

「acmsguru - 104」Little shop of flowers

设 $f(i,j)$ 为把前 $i$ 朵花放进前 $j$ 个花筒的最优。

转移即 $f(i,j)=\max\{f(i-1,j),f(i-1,j-1)+a(i,j)\}$ ，记录路径即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=200;
int a[N][N],lst[N][N],dp[N][N],pas[N],tot;
signed main() {
	int n=read(),m=read();
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) a[i][j]=read();
	memset(dp,-0x3f,sizeof dp);
	for(int i=0; i<=m; ++i) dp[0][i]=0;
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) {
		if(dp[i][j-1]>dp[i-1][j-1]+a[i][j]) dp[i][j]=dp[i][j-1],lst[i][j]=-1;
		else dp[i][j]=dp[i-1][j-1]+a[i][j],lst[i][j]=1;
	}
	printf("%d\n",dp[n][m]);
	function<void(int,int)> DIGUI=[&](int n,int m) {
		if(n==0) return;
		if(lst[n][m]==1) DIGUI(n-1,m-1),pas[++tot]=m;
		else if(lst[n][m]) DIGUI(n,m-1);
	};
	DIGUI(n,m);
	for(int i=1; i<=tot; ++i) printf("%d ",pas[i]);
	return 0;
}

「acmsguru - 105」Div 3

被 $3$ 除的仂分布是 $1,2,0,1,2,0,\dots$ 。然后答案显然是 $\lfloor\frac{n}{3}\rfloor\times+[n\bmod3=2]$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
signed main() {
	int n=read();
	printf("%d\n",n/3*2+(n%3==2));
	return 0;
}

「acmsguru - 106」The equation

拓欧板子，没啥意义蒯仂个代码交了。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll long long int
#define mod 1000000007
#define ceils(a,b) ceil(double(a)/double(b))
#define floors(a,b) floor(double(a)/double(b))
using namespace std;
ll extend(ll a,ll b,ll &x,ll &y)
{
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    else{
        ll t=extend(b,a%b,x,y);
        ll c=x;
        x=y;
        y=c-a/b*y;
        return t;
    }
}
int main(){
    ll a,b,c,x1,x2,y1,y2;
    ll x,y,k1,k2,k3,k4,d,g;
    cin>>a>>b>>c>>x1>>x2>>y1>>y2;
    if(!(x1<=x2&&y1<=y2)) cout<<0<<endl;
    else if(a==0&&b==0) cout<<(c==0)*(x2-x1+1)*(y2-y1+1)<<endl;
    else if(a==0){
        y=-c/b;
        cout<<((b*y+c==0)&&(y1<=y&&y<=y2))*(x2-x1+1)<<endl;
    }
    else if(b==0){
        x=-c/a;
        cout<<((a*x+c==0)&&(x1<=x&&x<=x2))*(y2-y1+1)<<endl;
    }
    else{
        g=extend(a,b,x,y);
        if(c%g==0){
            a/=g;b/=g;c/=g;
            x*=-c;y*=-c;
            if(b>0){
                k1=ceils(x1-x,b);
                k2=floors(x2-x,b);
            }
            else{
                k1=ceils(x2-x,b);
                k2=floors(x1-x,b);
            }
            if(a<0){
                k3=ceils(y-y1,a);
                k4=floors(y-y2,a);
            }
            else{
                k3=ceils(y-y2,a);
                k4=floors(y-y1,a);
            }
            ll mi=min(k2,k4);
            ll ma=max(k1,k3);
            if(mi>=ma) cout<<mi-ma+1<<endl;
            else cout<<0<<endl;
        }
        else cout<<0<<endl;
    }
    return 0;
}

「acmsguru - 107」987654321 problem

打个表知道 $n\geqslant9$ 时有 $9$ 个解：111111111;119357639;380642361;388888889;611111111;619357639;880642361;888888889

然后就考虑往高位填数，填 $1$ 个 $(0,9]$ 和 $n-10$ 个 $[0,9]$ ，答案显然。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
signed main() {
	int n=read();
	if(n<9) puts("0");
	else {
		printf("%d",8*int(pow(9,n!=9)));
		for(int i=1; i<=n-10; ++i) printf("0");
	}
	return 0;
}

「acmsguru - 108」Self-numbers 2

可以直接筛出来，然后循环利用卡卡空间，真的是＊＊非要这么卡。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=5100,yu=1000;
struct Item { int x,i; } s[N];
signed main() {
	int m=read(),n=read();
	for(int i=0; i<n; ++i) s[i]=Item{(int)read(),i};
	sort(s,s+n,[](Item a,Item b){return a.x<b.x;});
	static int lt,rt,ans[N]; static bool lst[yu],nxt[yu];
	memset(lst,1,sizeof lst),memset(nxt,1,sizeof nxt);
	for(int i=1; i<=m; ++i) {
		if(i%yu==0) memcpy(lst,nxt,yu),memset(nxt,1,sizeof nxt);
		if(lst[i%yu]) {
			++lt;
			while(s[rt].x==lt) ans[s[rt++].i]=i;
		}
		int tp=0;
		for(int j=i; j; j/=10) tp+=j%10;
		if(tp+(i%yu)>=yu) nxt[(tp+(i%yu))%yu]=0;
		else lst[tp+(i%yu)]=0;
	}
	printf("%d\n",lt);
	for(int i=0; i<n; ++i) printf("%d ",ans[i]);
	return 0;
}

「acmsguru - 109」Magic of David Copperfield II

大约是用 $(i+j)\&1$ 来构造，先跳了。

Oops, something went wrong.

「acmsguru - 110~119」

「acmsguru - 110」Dungeon

计几，不会，爬了。

「acmsguru - 111」Very simple problem

二分，高精用 Python。

n=int(input())
l=0
r=n
ans=-1
while l<=r:
    mid=(l+r)//2
    if mid*mid<=n:
        l=mid+1
        ans=mid
    else:
        r=mid-1
print(ans)

「acmsguru - 112」a^b - b^a

没营养。

a,b=input().split()
a,b=int(a),int(b)
print(a**b-b**a)

「acmsguru - 113」Nearly prime numbers

枚举因数，考虑快速判断质数。大数直接判，小数线性筛打表。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
signed main() {
	static bool vis[1000100];
	auto Prime=[&](int n=1000000) {
		static int pr[1000100];
		for(int i=2; i<=n; ++i) {
			if(!vis[i]) pr[++pr[0]]=i;
			for(int j=1; j<=pr[0]&&i*pr[j]<=n; ++j) {
				vis[i*pr[j]]=1;
				if(i%pr[j]==0) break;
			}
		}
	};
	Prime();
	auto ck=[&](ll x) {
		if(x<=1000000) return !vis[x];
		for(ll i=2; i*i<=x; ++i)
			if(x%i==0) return false;
		return true;
	};
	for(int T=read(); T; --T) {
		int n=read(),cnt=0;
		for(int i=2; i*i<=n; ++i)
			if(n%i==0) {
				if(ck(i)&&ck(n/i)) {cnt=2; break;}
				else break;
			}
		puts(cnt==2?"Yes":"No");
	}
	return 0;
}

「acmsguru - 114」Telecasting station

求解 $\sum|x_{i}-x_{0}|\times p_{i}$ ，带权中位数即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=15100;
struct st {double a; ll b;} s[N]; ll sum,cur;
signed main() {
	int n=read();
	for(int i=0; i<n; ++i) cin>>s[i].a,s[i].b=read(),sum+=s[i].b;
	sort(s,s+n,[](st x,st y){return x.a<y.a;});
	for(int i=0; i<n; ++i) if((cur+=s[i].b)*2>=sum) return printf("%.5f\n",s[i].a),0;
	return 0;
}

「acmsguru - 115」Calendar

模拟。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int dys[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
signed main() {
    int n=read(),m=read();
    if(n<1||m<1||m>13||n>dys[m]) return puts("Impossible"),0;
    int sum=n;
    for(int i=1; i<m; ++i) sum+=dys[i];
    printf("%d\n",sum%7==0?7:sum%7);
    return 0;
}

「acmsguru - 116」Index of super-prime

首先把 Super-Primes 筛出来，然后完全背包记录转移。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=10100;
int prime[N],tot,super[N],cnt,dp[N],lst[N];
signed main() {
    auto shai=[&](int n) {
        static int vis[N];
        for(int i=2; i<=n; ++i) {
            if(!vis[i]) prime[++tot]=i;
            for(int j=1; j<=tot&&prime[j]*i<=n; ++j) {
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
        for(int i=1; i<=tot&&prime[i]<=tot; ++i) super[++cnt]=prime[prime[i]];
    };
    int n=read(); shai(n);
    memset(dp,0x3f,sizeof dp),dp[0]=0;
    for(int i=1; i<=cnt; ++i) for(int j=super[i]; j<=n; ++j)
        (dp[j-super[i]]+1<dp[j])&&(dp[j]=dp[j-super[i]]+1,lst[j]=i);
    if(dp[n]==0x3f3f3f3f) puts("0");
    else {
        printf("%d\n",dp[n]);
        while(n) printf("%d ",super[lst[n]]),n-=super[lst[n]];
    }
    return 0;
}

「acmsguru - 117」Counting

快速幂板。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
ll QuickPow(ll base,int times,int MOD) {
    ll res=1;
    for(; times; times>>=1,base=base*base%MOD)
        (times&1)&&(res=res*base%MOD);
    return res;
}
signed main() {
    int n=read(),m=read(),k=read(),ans=0;
    for(int i=1; i<=n; ++i) ans+=QuickPow(read(),m,k)==0;
    printf("%d\n",ans);
    return 0;
}

「acmsguru - 118」Digital root

首先设 $n=$$\over{a[m]a[m-1]\dots a[1]}$ ，然后易证 $n\equiv \sum a[i](\operatorname{mod}~9)$ 。

于是把每个元素模个 $9$ ，然后就直接可以获得它的 $f(n)$ ，注意取模后结果为 $0$ 的话其值为 $9$ 。

也就是说 $f(n)=(n+8)\bmod9+1$ ， $f(\prod a[i])=(\prod a[i]+8)\bmod9+1$ ，好算了吧。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
signed main() {
    for(int T=read(); T; --T) {
        int n=read(); ll ans=0;
        for(ll i=0,s=1; i<n; ++i) s*=read(),s%=9,ans+=s,ans%=9;
        printf("%lld\n",ans%9?ans%9:9);
    }
    return 0;
}

「acmsguru - 119」Magic pairs

显然有循环节，先把 $a,b$ 模 $n$ ，然后分别的循环节就是 $\frac{n}{\gcd(a,n)},\frac{n}{\gcd(b,n)}$ 。求个 $\text{lcm}$ 即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
signed main() {
    ll n=read(),a=read()%n,b=read()%n;
    ll A=n/__gcd(a,n),B=n/__gcd(b,n);
    ll c=A/__gcd(A,B)*B;
    vector<pair<ll,ll>> ans;
    for(ll i=0; i<c; ++i) ans.push_back({a*i%n,b*i%n});
    sort(ans.begin(),ans.end());
    printf("%d\n",int(ans.size()));
    for(auto [x,y]:ans) printf("%lld %lld\n",x,y);
    return 0;
}

「acmsguru - 120~129」

「acmsguru - 120」Archipelago

计几，不会，跳了。

Oops, something went wrong.

「acmsguru - 121」Bridges painting

充分暴露出我智商不足。直接 DFS 交替构造。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=200;
vector<int> G[N];
signed main() {
    static int n=read(),deg[N],co[N][N];
    memset(co,-1,sizeof co);
    for(int i=1; i<=n; ++i) for(int x; x=read();) G[i].push_back(x),++deg[i];
    function<void(int,int)> dfs=[&](int x,int c) {
        c^=1;
        for(int y:G[x]) if(co[x][y]==-1) co[x][y]=co[y][x]=c,dfs(y,c),c^=1;
    };
    for(int i=1; i<=n; ++i) if(deg[i]&1) dfs(i,0);
    for(int i=1; i<=n; ++i) dfs(i,0);
    for(int i=1; i<=n; ++i) if(deg[i]>1) {
        bool zr=0,on=0;
        for(int x:G[i]) zr|=(co[i][x]==0),on|=(co[i][x]==1);
        if(!zr||!on) return puts("No solution"),0;
    }
    for(int i=1; i<=n; ++i,puts("0")) for(int x:G[i]) printf("%d ",co[i][x]+1);
    return 0;
}

「acmsguru - 122」The book

Hamilton 回路板题，有空补补这个知识点。

Oops, something went wrong.

「acmsguru - 123」The book

？？？这什么智障题？

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
ll fib[50];
signed main() {
    int n=read();
    fib[1]=fib[2]=1;
    for(int i=3; i<=n; ++i) fib[i]=fib[i-1]+fib[i-2];
    printf("%lld\n",accumulate(fib+1,fib+n+1,0));
    return 0;
}

「acmsguru - 124」Broken line

哪来这么多计算几何！！

// Oops, something went wrong.

「acmsguru - 125」Shtirlits

注意到 $F$ 中一定包含 $0$ （一定存在至少一个最大值），然后所有 $\forall (i,j),s.t.F(i,j)=0$ ，可以推出 $G(i,j)=n^{2}$ ，然后把 $(i,j)$ 周围的非零 $F$ 减一，把变成零的 $F$ 加入零的队伍。

DFS 搜即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=50;
int a[N][N],ans[N][N],vis[N][N];
signed main() {
    int n=read(),k=n*n; memset(a,-1,sizeof a);
    queue<pair<int,int>> q;
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) ((a[i][j]=read())==0)&&(q.push({i,j}),ans[i][j]=k);
    const vector<pair<int,int>> dir{{1,0},{-1,0},{0,1},{0,-1}};
    function<void(int,int,int)> fs=[&](int x,int y,int k) {
        for(auto [dx,dy]:dir) {
            auto [nx,ny]=make_pair(x+dx,y+dy);
            if(a[nx][ny]==0) ans[nx][ny]=k,a[nx][ny]=-1,vis[nx][ny]=1,fs(nx,ny,k);
            else if(a[nx][ny]>0&&!(--a[nx][ny])) q.push({nx,ny});
        }
    };
    for(; q.size(); q.pop(),--k) {
        auto [x,y]=q.front();
        if(!vis[x][y]) vis[x][y]=1,ans[x][y]=k,a[x][y]=-1,fs(x,y,k);
    }
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) if(!ans[i][j]) return puts("NO SOLUTION"),0;
    for(int i=1; i<=n; ++i,puts("")) for(int j=1; j<=n; ++j) printf("%d ",ans[i][j]);
    return 0;
}

「acmsguru - 126」Boxes

结论是 $\frac{a+b}{\gcd(a,b)}$ 是否为 $2^{k}$ ，如果是答案就是 $k$ ，否则无解。

不会证明。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
int main() {
    ll a=read(),b=read(),g=__gcd(a,b);
    a/=g,b/=g;
    for(ll k=0; k<33; ++k) if((1ll<<k)==a+b) return printf("%d\n",k),0;
    puts("-1");
    return 0;
}

「acmsguru - 127」Telephone directory

我看不懂，但我大受震撼。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
int cnt[10];
signed main() {
    int k=read(),n=read(),ans=2;
    for(; n--;) ++cnt[read()/1000];
    for(int i=1; i<10; ++i) (cnt[i])&&(((cnt[i]%k==0)&&(ans+=cnt[i]/k)),((cnt[i]%k)&&(ans+=cnt[i]/k+1)));
    printf("%d\n",ans);
    return 0;
}

「acmsguru - 128」Snake

计算几何。

Oops, something went wrong.

「acmsguru - 129」Inheritance

这神笔题库哪来这么多计几？？？

Oops, something went wrong.

「acmsguru - 130~139」

「acmsguru - 130」Circle

设 $f(i)$ 为 $k=i$ 时的答案，转移即 $f(i)=\sum_{j=0}^{i-1}f(j)f(i-j-1)$ ，边界 $f(0)=f(1)=1$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
ll dp[50];
signed main() {
    int n=read();
    dp[1]=dp[0]=1;
    for(int i=2; i<=n; ++i)
        for(int j=0; j<i; ++j) dp[i]+=dp[j]*dp[i-j-1];
    printf("%lld %lld\n",dp[n],n+1);
    return 0;
}

「acmsguru - 131」Hardwood floor

不太会这种难写的状压啊，以后补吧。

「acmsguru - 132」Another Chocolate Maniac

不太会这种难写的状压啊，以后补吧。

「acmsguru - 133」Border

排序。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=16100;
signed main() {
	int n=read();
	vector<pair<int,int>> vec(n);
	for(auto &[x,y]:vec) x=read(),y=read();
	sort(vec.begin(),vec.end());
	int ans=0,mx=vec.begin()->second;
	for(auto i=0u; i<vec.size(); ++i) (vec[i].second<mx)&&(++ans),(vec[i].second>mx)&&(mx=vec[i].second);
	printf("%d\n",ans);
	return 0;
}

「acmsguru - 134」Centroid

点分治基础练习题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=16100;
int dp[N],n,sz[N],rt;
vector<int> G[N];
void dfs(int x,int las) {
	sz[x]=1; int mx=0;
	for(int y:G[x]) if(y!=las) {
		dfs(y,x),sz[x]+=sz[y];
		dp[x]=max(dp[x],sz[y]);
	}
	dp[x]=max(dp[x],n-sz[x]);
	if(dp[x]<dp[rt]) rt=x;
}
signed main() {
	n=read(),dp[0]=n+1;
	for(int i=1,x,y; i<n; ++i) x=read(),y=read(),G[x].push_back(y),G[y].push_back(x);
	dfs(1,0);
	vector<int> rid;
	for(int i=1; i<=n; ++i) if(dp[i]==dp[rt]) rid.push_back(i);
	printf("%d %d\n",dp[rt],(int)rid.size());
	for(int x:rid) printf("%d ",x);
	return 0;
}

「acmsguru - 135」Drawing Lines

仔细观察，答案为 $\frac{i(i+1)}{2}+1$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
signed main() {
	ll tmp=read();
	printf("%lld\n",(tmp+1)*tmp/2+1);
	return 0;
}