本文共 2354 字，大约阅读时间需要 7 分钟。

A. Shovels and Swords

题解：

假设第一种工具买了x个,第二种买了y个。 那么由题可知 $0\le 2x+y\le a$ $0\le x+2y\le b$ 求(x+y)max，高中线性规划可以求解。

int main(){   	int t;	cin >> t;	while(t--)	{   		ll a,b;		cin >> a >> b;		if(2*min(a,b)<=max(a,b))			cout << min(a,b) << endl;		else cout << (a+b)/3 << endl;	}}

---

B. Shuffle

题解：区间合并，如果有交集就不断扩大左右边界，最后求区间长度即可。

int main(){   	int t;	cin >> t;	while(t--)	{   		ll n,m,x;		cin >> n >> x >> m;		ll L=x,R=x;		for(int i=0;i
   
    > l >> r;			if(l<=R && L<=r)			{   				L=min(L,l);				R=max(R,r);			}		}		cout << R-L+1 << endl;	}}
   

---

C. Palindromic Paths

题解：

emmm,找规律吧，由于从(1,1)到达(n,m)的路径必须是回文串，那么可以理解为从(1,1)出发第m步全部能到达的点必须全部等于从(n,m)出发往(1,1)走时第m步全部能到达的点，那么很容以得出一个结论：就是(1,1)出发第m步全部能到达的点和从(n,m)出发往(1,1)走时第m步全部能到达的点必须全部一致，倘若有一个不一致，那么去时在第m步选择为0，距离终点m步时选择为1的点就不满足回文串要求，知道这个去模拟即可。

int a[35][35];//map
   
     mp,mp1;int mp[10005],mp1[10005];int main(){   	int t;	cin >>t;	while(t--)	{   		memset(mp, 0, sizeof(mp));		memset(mp1, 0, sizeof(mp1));		int n,m;		cin >> n >> m;		for(int i=1;i<=n;i++)			for(int j=1;j<=m;j++) cin >> a[i][j];		int ans=0,sum=2+n+m;		for(int i=1;i<=n;i++)			for(int j=1;j<=m;j++)			{   				if((n+m)%2==0 && i+j==(n+m)/2+1) continue;				if(a[i][j]) 				{   					if(i+j>sum/2) mp[sum-(i+j)]++;					else mp[i+j]++;				}				else 				{   					if(i+j>sum/2) mp1[sum-(i+j)]++;					else mp1[i+j]++;				}			}		for(int i=2;i<=sum/2;i++) ans+=min(mp[i],mp1[i]);		cout << ans << endl;	}}
   

---

D. Two Divisors

题解：

这题很坑，以至于好多人被叉了(包括我)，这个题貌似只能用唯一分解定理去搞，由于a[i]≤1e7，即使$n\ast \sqrt{n}时间复杂度也会超时$. 题目要求找一个数的2个>1的因子，使得gcd(d1+d2,a)==1，其实由裴蜀定理可知 gcd(d1+d2,a)==1 ⇒ k1*(d1+d2)+k2*a=1 (k1,k2为整数) 易知a=k3*d1 (k3为整数) (k1+k2*k3)d1+k1*d2=1 ⇒ k’*d1+k’’*d2=1 (其中k’=(k1+k2*k3),k’’=k1) 由裴蜀逆定理可知 gcd(d1,d2)=1即可 言外之意，找两个大于1且互质的因子即可。 这里有个技巧在欧拉筛完素数时，可以用一个数组mp记录每一个数最小质因子p，将一个数可以表示为x=$p^k\ast p1，此时d1=p^k,d2=p1，判断d1,d2是否为1即可。$

pii d[maxn];int vis[maxm];int prime[maxm];int mp[maxm];void getprime(){   	vis[0]=vis[1]=1;	for(int i=2;i
   
    1)		{   			while(a%tmp==0)			{   				a/=tmp;				y*=tmp;			}		}		if(a>1 && y>1)		{   			d[i].fi=a;d[i].se=y;		}		else{   			d[i].fi=-1;			d[i].se=-1;		}	}	for(int i=1;i<=n;i++)		printf("%d ",d[i].first);	printf("\n");	for(int i=1;i<=n;i++)		printf("%d ",d[i].second);}
   

转载地址：http://comh.baihongyu.com/