洛谷10月月赛(100+40+70+0)代码

阅读量：5236 次

发布时间：2019-06-14

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

T48748 [1007]魔法少女小Scarlet

题目描述

Scarlet最近学会了一个数组魔法，她会在

首先，Scarlet会把 $11到n^2n2的正整数按照从左往右，从上至下的顺序填入初始的二维数组中，然后她会施放一些简易的魔法。$

Scarlet既不会什么分块特技，也不会什么Splay套Splay，她现在提供给你她的魔法执行顺序，想让你来告诉她魔法按次执行完毕后的二维数组。

输入输出格式

输入格式：

第一行两个整数

接下来

输出格式：

输出

输入输出样例

输入样例#1：

5 42 2 1 03 3 1 14 4 1 03 3 2 1

输出样例#1：

5 10 3 18 154 19 8 17 201 14 23 24 256 9 2 7 2211 12 13 16 21

说明

对于50%的数据，满足

对于100%的数据 $1\leq n,m\leq5001≤n,m≤500，满足1\leq x-r\leq x+r\leq n,1\leq y-r\leq y+r\leq n1≤x−r≤x+r≤n,1≤y−r≤y+r≤n$

/*可以想象为对每个中心都建立一个坐标系然后旋转，横纵坐标分情况交换取反 */#include
     
      #include
      
       #include
       
        #define N 507using namespace std;int a[N][N], b[N][N];int n,m;inline int read(){    int x=0,f=1;char c=getchar();    while(c>'9'||c<'0'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}void solve1(int x, int y, int r, int opt){    memcpy(b, a, sizeof(b));    for(int i=x-r;i<=x+r;i++)    {        for(int j=y-r;j<=y+r;j++)        {            int dx=j-y,dy=x-i;swap(dx,dy);            dy=-dy;b[x-dy][y+dx]=a[i][j];        }    }    memcpy(a, b, sizeof(b));}void solve2(int x, int y, int r, int opt){    memcpy(b, a, sizeof(b));    for(int i=x-r;i<=x+r;i++)    {        for(int j=y-r;j<=y+r;j++)        {            int dx=j-y,dy=x-i;swap(dx,dy);            dx=-dx;b[x-dy][y+dx]=a[i][j];        }    }    memcpy(a, b, sizeof(b));}int main(){    n=read();m=read();    int tot = 0;    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j] = ++tot;    for(int i=1;i<=m;i++)    {        int x = read(), y=read(),r=read(),opt=read();        if(opt == 0) solve1(x, y, r, opt);        else solve2(x, y, r, opt);            }    for(int i=1;i<=n;i++)  for(int j=1;j<=n;j++)    {        printf("%d ",a[i][j]);        if(j==n) printf("\n");    }    return 0;}

T48749 [1007]Scarlet的字符串不可能这么可爱

题目描述

Scarlet妄图构造字符集为

看起来这样的字符串太多了，Scarlet随手加了个限制：她指定了字符串的第

这下Scarlet不会做了，请你来帮她计算究竟有多少满足条件的字符串。按照套路，你只要求出答案对

输入输出格式

输入格式：

第一行三个整数

第二行两个整数

注意：

输出格式：

一行一个整数，表示答案对

输入输出样例

输入样例#1：

3 3 2331 1

输出样例#1：

说明

字符集：一个字符串中不同字符的数量。例如，字符集是3的话，你可以认为字符串仅由“A”、“B”、“C”三个字母组成。

样例解释：第一个字符固定A，那么符合要求的字符串是ABC,ACB。而AAB字符串包括AA这个回文子串，ACA本身就是回文串，一次类推。

对于50%的数据， $k\leq5,L\leq10k≤5,L≤10$

对于另30%的数据，

对于100%的数据 $1\leq k,L\leq 10^{18},0\leq s\leq L,1\leq w\leq k,1\leq p\leq 10^91≤k,L≤1018,0≤s≤L,1≤w≤k,1≤p≤109$

/*40分 dfs map判重 开O2都跑不过第五个点 ...*/ #include
     
      #include
      
       #include
       
        #include
        #define N 107#define ll long longusing namespace std;int n,ans,k,l,p,s,w;int vis[N],str[N];map
         
          v;bool judge(){    for(int i=1;i
          
           >k>>l>>p>>s>>w; if(l<=k && s!=0) { k--;l--; printf("%d\n",((A(k)%p)*(l-k+1))%p); return 0; } else { for(int i=1;i<=k;i++) { memset(vis,0,sizeof v);memset(str,0,sizeof str); vis[s]=1;str[s]=w; if(s!=1)str[1]=i;vis[1]=1;dfs(1,i); } ans%=p; cout<
           
            <

/*貌似计算时每一个位置都只跟它上一个和上上个有关*/#include 
      
       #define maxn 2000using namespace std;typedef long long LL;#define G c=getchar()inline LL read(){    LL x=0,f=1;char G;    while(c>57||c<48){
    if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}LL Pow(LL a,LL b,LL p){    LL r=1;    for(;b;b>>=1,a=a*a%p)        if(b&1)r=r*a%p;    return r;}LL k,L,p,s,w;LL work(){    if(s==0)        if(L==1)            return k;        else if(L==2)            return k*(k-1)%p;        else            return k*(k-1)%p*Pow(k-2,L-2,p)%p;    else        if(L==1)            return 1;        else if(L==2)            return k-1;        else            return (k-1)*Pow(k-2,L-2,p)%p;}int main(){    k=read(),L=read(),p=read(),s=read(),w=read();    k%=p;    printf("%lld\n",work());    return 0;}

std

T48750 [1007]倍杀测量者

题目描述

今天Scarlet在机房有幸目睹了一场别开生面的OI训练。因为一些奇妙的SPJ，比赛中所有选手的得分都是正实数（甚至没有上限）。

当一位选手A的分数不小于选手B的分数

更奇妙也更激动人心的是，训练前有不少选手立下了诸如“我没

知道真相的良心教练Patchouli为了维持机房秩序，放宽了选手们的Flag限制。Patchouli设定了一个正常数

提前知道了某些选手分数和具体Flag的Scarlet实在不忍心看到这么一次精彩比赛却没人女装，为了方便和Patchouli交易，Scarlet想要确定最大的实数

输入输出格式

输入格式：

第一行三个整数

接下来

输出格式：

若存在能保证赛后有选手女装的最大的T，则输出T，只有当输出与答案的绝对误差不超过 $10^{-4}10−4时才被视作正确输出。$

若不存在，输出"-1"（去掉引号）

输入输出样例

输入样例#1：

3 5 11 2 1 21 3 2 21 3 1 42 1 2 22 1 3 41 1

输出样例#1：

-1

输入样例#2：

3 2 31 2 1 102 2 3 61 12 63 9

输出样例#2：

3.9999993984

说明

对于30%的数据， $1\leq n\leq5,1\leq s\leq 21≤n≤5,1≤s≤2$

对于另40%的数据，保证

对于100%的数据， $1\leq n,s\leq 1000,1\leq A,B,C,t\leq n,1\leq k\leq 10,1\leq x\leq 10^91≤n,s≤1000,1≤A,B,C,t≤n,1≤k≤10,1≤x≤109。保证输入中的CC两两不同。$

/*70分 询问离线二分答案不清楚为什么挂掉30 */#include
     
      #include
      
       #include
       
        #define N 1007#define ll long longusing namespace std;ll n,s,t,x,y,ans,cnt,flag;ll point[N];struct ask{    int o,A,B,k;}a[N];bool judge(double T){    for(int i=1;i<=n;i++)    {        if(!point[a[i].A] || !point[a[i].B]) continue;        if(a[i].o==1)        {            if(a[i].k-T<0) continue;            if(point[a[i].A]
        
         >n>>s>>t;    for(int i=1;i<=s;i++)    cin>>a[i].o>>a[i].A>>a[i].B>>a[i].k;    for(int i=1;i<=t;i++)    {        cin>>x>>y;        point[x]=y;    }    double l=0,r=10000000000,eps=0.00000000001;    while(r-l>=eps)    {        double mid=(l+r)/2;        if(judge(mid)) l=mid;        else r=mid;    }    if(flag) printf("%.11lf\n",l);    else puts("-1");    return 0;}