NOIP模拟赛

。。。。。我选择死亡。。。。。。。。。。。。。。。。。

 


发现看错题目了。。。。。。。。。。。。。。。。。

居然想成了第一天第1个仆人打扫第一个房间。。。。。。。。。。。智商菌持续掉线中。。。。。

XX城堡有n个房间, 每个房间都被装饰成一种颜色( 房间颜色可以重
复),记第i个房间的颜色为ci,外面的人无法进入这个城堡,但是可以通过 里面的仆人了解到这些房间的颜色。这些仆人正好有n个,他们要打扫这些 房间。他们有奇怪的规则:第一天第i个仆人打扫第i
个房间,第二天第i个仆 人打扫第i + 1个房间(若i = n,则他打扫第1个房间),第三天第i个仆人打 扫第i + 2个房间(若i = n − 1,他打扫第1个房间:若i = n,他打扫第2个房
间),以此递推循环下去。每个仆人都有自己最喜欢的颜色,当他打扫一个房 间后,他会告诉你这个房间颜色是不是c(c为这个仆人最喜欢的颜色)。某人
对这个城堡很有兴趣,你想知道他在第几天才能完全了解到所有房间的颜色。
【输入】
输入文件为color.in。 输入有3行,第一行有一个正整数n。第二行有n个整数,表示每个房间的
颜色。第三行有n个整数,表示每个仆人最喜欢的颜色。

【输出】
输出文件为color.out。 输出只有一个正整数,如题所述:如果答案为无穷大,请输出−1。
【输入输出样例1】

color.in color.out
4
1 2 3 4
4 3 2 1
4

【样例1解释】
第一天仆人不会说出什么有用的信息,第二天第一个房间和第三个房间的 颜色会被知道,第三 天不会有什么有用信息,第四天第二个房间和第四个房间 的颜色会被知道,故答案为 4。
【输入输出样例2】

color.in color.out
3
1 2 3
1 2 2
-1

【数据范围】
对于50%的数据,0 < n ≤ 1000;
对于100%的数据,0 < n ≤ 100000, 0 ≤ c, ci ≤ 1000000.

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 1500000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
    return x*f;
}
int n,f[maxn],head[maxn];
struct edge{int go,next;}e[maxn];
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    n=read();
    for1(i,n)
    {
        int x=read();
        e[i].go=i;e[i].next=head[x];head[x]=i;
        f[i]=inf;
    }
    for1(i,n)
    {
        int x=read();
        for(int j=head[x];j;j=e[j].next)
         {
             int y=e[j].go;
             if(y>=i)f[y]=min(f[y],y-i+1);else f[y]=min(f[y],n-i+y+1);
         }
    }
    int ans=1;
    for1(i,n)ans=max(ans,f[e[i].go]);
    printf("%d\n",ans==inf?-1:ans);
    return 0;
}

 


T2

两次SPFA。。。。。。。。。。

智商菌依然持续下线

此条目发表在JCYZOJ分类目录。将固定链接加入收藏夹。