【题解】10-2入门组模拟

谁能有我tang，我T2循环次数开小了，只拿了8分，调大就过了，真tm服了啊

A.【MX-J1-T2】『FLA - III』Ilumina

link

这道是数学题，给我整sha了，我数学题贼不好。

我么们可以将问题转化成判断是否存在正整数$m$使得$c=\left \lfloor \frac{a}{m} \right \rfloor$。

如果存在这样的$m$，因为构造中$n=1$，直接输出$a$即可。
$$
\left \lfloor \frac{a}{\left \lfloor \frac{a}{c}\right \rfloor}\right \rfloor \geq \left \lfloor \frac{a}{\frac{a}{c}}\right \rfloor=\lfloor c\rfloor =c=\left \lfloor \frac{a}{m}\right \rfloor
$$

存在合法的$m$当且仅当存在区间$[l,r]$满足$l \leq r$且对于$i \in [l,r] \cap \Z$有$\left \lfloor \frac{a}{i}\right \rfloor=c$。

很显然，最大的满足条件的$i$（使用$i_0$表示）满足$i_0 \times c \leq a$并且$(i_0+1)\times c>a$，容易得到$i_0=\lfloor \frac{a}{c}\rfloor$，计算$i_0$的值并且检验$\lfloor \frac{a}{i_0}\rfloor$是否等于$c$即可判断是否存在合法的$m$。

单组数据时间复杂度$O(1)$。

借鉴这篇题解

// Problem:Luogu P10782 【MX-J1-T2】『FLA - III』Ilumina

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int a,c;
		cin>>a>>c;
		if(a<c)puts("-1");
        else if(a/(a/c)==c)cout<<a<<endl;
        else puts("-1");
	}
}

B.[USACO3.1] 邮票 Stamps

link

这题就是纯纯正正的dp，感觉和这题很像

只需要把dp数组开的足够大，暴力寻找的次数足够大，就能ac了

// Problem:Luogu P2725 [USACO3.1] 邮票 Stamps

#include<bits/stdc++.h>
using namespace std;
int f[10000010],a[1000010],n,k;
int main()
{
	cin>>k>>n;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)cin>>a[i],f[a[i]]=1;
	for(int i=1;i<=9999999;i++)
	{
		for(int j=1;j<=n;j++)
			if(i-a[j]>=0)
				f[i]=min(f[i],f[i-a[j]]+1);
		if(f[i]>k)
		{
			cout<<i-1;
			return 0;
		}
	}
}

C.[JOI 2020 Final] JJOOII 2

link

这道题就是贪心+前缀和+二分（lower_bound）

用前缀和统计每个字母出现的位置，然后接下来往后找$k$个O和I

然后答案就是找出来最短的JOI串的长度减去$3 \times k$。

// Problem:Luogu P6878 [JOI 2020 Final] JJOOII 2

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int J[MAXN],O[MAXN],I[MAXN],n,k;
string s;
int main()
{
	cin>>n>>k>>s;
	for(int i=1;i<=n;i++)
	{
		J[i]=J[i-1];
		O[i]=O[i-1];
		I[i]=I[i-1];
		if(s[i-1]=='J')J[i]++;
		if(s[i-1]=='O')O[i]++;
		if(s[i-1]=='I')I[i]++;
	}
	int ans=INT_MAX;
	for(int i=1;i<=n;i++)
	{
        //其实并不需要把J、O、I全部都找到，只需要找到一个J就可以了
		if(s[i-1]!='J')continue;
		int x=lower_bound(J+1,J+1+n,J[i-1]+k)-J;
		int y=lower_bound(O+1,O+1+n,O[x-1]+k)-O;
		int z=lower_bound(I+1,I+1+n,I[y-1]+k)-I;
		if(x>n||y>n||z>n)break;
		ans=min(ans,z-i+1);
	}
	if(ans==INT_MAX)puts("-1");
	else cout<<ans-k*3;
	return 0;
}

D.[USACO20FEB] Clock Tree S

link

这道题是dfs

因为找起点的数量，就依次遍历

当奶牛从$u$走到$v$的时候，$u$和$v$的时钟都会往后拨一格，所以父子之间的差是固定的

那我们在$u$和$v$之间不断走动，使$v$变成$12$，然后让$u$与$u$的父亲进行操作。

最后到根节点为$12$就说明这个起点可行，根节点为$1$也是可以的，只要我们从根到它的儿子使它的儿子为$12$， 然后不返回也可以满足条件。

// Problem:Luogu P6150 [USACO20FEB] Clock Tree S

#include<bits/stdc++.h>
using namespace std;
const int MAXN=50010;
vector <int> g[MAXN];
int a[MAXN],b[MAXN],ans;
void dfs(int u,int fa)
{
	for(auto v:g[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		b[u]=(b[u]+12-b[v])%12;
        //用模数代表钟的状态
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		memcpy(b,a,sizeof(b));
		dfs(i,0);
		if(b[i]==0||b[i]==1)ans++;
       	//0和1都是可以的
	}
	cout<<ans;
	return 0;
}