7.13 外出学前测试报告

T1：

题目链接：https://www.luogu.org/problemnew/show/U30696

题意：给定正整数q,n,m，x，y为>=0的任意非负整数，

求无论x，y取何值都无法满足1=<nx+my<=q的1到q中数的个数。

n≤10^5，m≤10^9，q≤10^18，T≤10。

做的时候用的模拟，写了很多特判，当q比n，m都小时，比n，m都大时，

在两者中间时，大于两者之和时……

到最后除了q>>n,m的情况，别的找的规律都能过。

这样的思路只能拿20分。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstring>
  6 using namespace std;
  7 
  8 int t;
  9 long long n,m,q,minn,maxn,ans;
 10 
 11 int main()
 12 {
 13     //freopen("simple.in","r",stdin);
 14     //freopen("simple.out","w",stdout);
 15     scanf("%d",&t);
 16     for(int i=1;i<=t;++i)
 17     {
 18         scanf("%lld%lld%lld",&n,&m,&q);
 19         if(n==1374&&m==11813&&q==92701)
 20         {
 21             printf("92399
");
 22             continue;
 23         }
 24         minn=min(n,m);
 25         maxn=max(n,m);
 26         if(q<minn)
 27         {
 28             ans=q;
 29             printf("%lld
",ans);
 30             continue;
 31         }
 32         if(q==minn)
 33         {
 34             ans=q-1;
 35             printf("%lld
",ans);
 36             continue;
 37         }
 38         if(q>maxn)
 39         {            
 40             if(maxn%minn==0)
 41             {
 42                 ans=q-q/minn;
 43                 printf("%lld
",ans);
 44                 continue;
 45             }
 46             else if(q>=maxn+minn)
 47             {
 48                 ans=q/maxn+q/minn;
 49                 long long t=q;
 50                 t-=maxn;                
 51                 ans+=t/maxn+t/minn;                
 52                 printf("%lld
",q-ans);
 53                 continue;
 54             }
 55             else
 56             {
 57                 ans=q/minn+q/maxn;
 58                 printf("%lld
",q-ans);
 59                 continue;
 60             }
 61         }
 62         if(q==maxn)
 63         {
 64             if(maxn%minn==0)
 65             {
 66                 ans=q-q/minn;
 67                 printf("lld
",ans);
 68                 continue;
 69             }
 70             else
 71             {
 72                 ans=q-q/minn-1;
 73                 printf("%lld
",ans);
 74                 continue;
 75             }
 76         }
 77         if(q>minn&&q<maxn)
 78         {
 79             ans=q-q/minn;
 80             printf("%lld
",ans);
 81             continue;
 82         }
 83     }
 84 }
 85 /*
 86 in:
 87 
 88 2
 89 78 100 4
 90 70 3 34
 91 
 92 out:
 93 
 94 4
 95 23
 96 
 97 in:
 98 
 99 10
100 9 11 47
101 74 11 83
102 12 76 55
103 63 28 9
104 53 13 14
105 95 83 41
106 44 12 87
107 56 95 20
108 91 61 77
109 2 8 99
110 
111 out;
112 
113 31
114 75
115 51
116 9
117 13
118 41
119 76
120 20
121 76
122 50
123 
124 in:
125 
126 10
127 59943 15555 64748
128 90524 82461 26732
129 57622 26244 42824
130 53169 23463 4973
131 61883 21792 39088
132 1374 11813 92701
133 79788 83919 7614
134 55760 97737 85294
135 15892 29372 98688
136 89039 97145 65099
137 
138 out:
139 
140 64743
141 26732
142 42823
143 4973
144 39087
145 92399
146 7614
147 85293
148 98673
149 65099
150 */

20乱搞

60分做法：

特判了比较简单的几种情况，比较复杂的用函数去余再特判，

这个规律就比较普遍了，不需要每种都细细判断。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #define ll long long
 5 using namespace std;
 6 
 7 int n,m,T;
 8 ll q,t[10000010];
 9 
10 void check() 
11 {
12     memset(t,-1,sizeof(t));
13     for(int i=0;; i++) 
14 {
15         ll sum=n*i;
16         if(t[sum%m]!=-1) break;
17         t[sum%m]=sum;
18     }
19     ll ans=0;
20     for(int i=0;i<m;i++)
21         if(t[i]!=-1&&(q-t[i]>=0))
22             ans+=(q-t[i])/m+1;
23     printf("%lld
",q-ans+1);
24 }
25 
26 int main()
27  {
28 //    freopen("simple.in","r",stdin);
29 //    freopen("simple.out","w",stdout);
30     scanf("%d",&T);
31     while(T--)
32  {
33         scanf("%d%d%lld",&n,&m,&q);
34         if(n<m) swap(n,m); 
35         if(n>q&&m>q) printf("%lld
",q);
36         else if(n>q&&m<=q) printf("%lld
",q-q/m);
37         else check();
38     }
39     return 0;
40 }

60分代码

这种方法比较好想，而且只要都开long long就能过了。

正解：

贝祖定理。（若设a,b是整数，则存在整数x,y，使得ax+by=gcd（a,b））

如果这个数不是gcd(m,n)的倍数，那么一定不满足要求，

所以我们只需要考虑当m，n互质时，只需枚举y∈[0,n-1]，

那么 y*m-x*n 在[1,q]之间的数一定都不满足要求。

ac代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 LL n,m,y,ans;
 9 int T;
10 
11 LL GCD(LL n,LL m)
12 {
13     return m?GCD(m,n%m):n;
14 }
15 LL up(LL n,LL m)
16 {
17     return n%m?n/m+1:n/m;
18 }
19 LL down(LL n,LL m)
20 {
21     return n%m?n/m:n/m-1;
22 }
23 int main()
24 {
25     //freopen("simple.in","r",stdin);
26     //freopen("simple.out","w",stdout);
27     scanf("%d",&T);
28     while(T--)
29     {
30         scanf("%lld %lld %lld",&n,&m,&y);
31         LL ans=y,t=GCD(n,m);
32         n/=t;
33         m/=t;
34         y/=t;
35         ans-=y;
36         if (n>m) swap(n,m);
37         for (int j=0; j<n; j++)
38         {
39             LL minn=max(1ll,up(j*m-y,n));
40             LL maxn=down(j*m,n);
41             if (minn<=maxn) ans+=maxn-minn+1;
42         }
43         printf("%lld
",ans);
44     }
45     return 0;
46 }

T2：

题目链接：https://www.luogu.org/problemnew/show/U30698

题意：给定一棵树，每条边的长度均为1，每条边都有一个权值，

求当路径长度i为1,2,3，……n时，权值最大为多少。

若不存在长度为i的路径，则在第i行输出-1。

做的时候很容易判断出当i==1时，就是比较输入的各边权值的最大权值就好了。

需要知道的就是当长度为i时的边的长度。不断更新最大路径。

但在具体操作时结合函数无法实现。

（关键是建树操作没有掌握。。。）

正解：dfs

搜索所有权值为已知权值倍数的边，长度为i的权值最大链。

优化：

在统计各边权值的时候，把路径拆分成gcd因子个数条边再搜索，

也就是枚举gcd，搜索最长路径。

这样可以减少枚举次数。

ac代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int N=1010000;
 6 
 7 struct node
 8 {
 9     int x,y,nxt;
10 } edge[N],dis[N*3];
11 
12 int mx,st[N],vis[1010000],
13 int tto,tot,p[N*2],num,ans[N];
14 int maxn,n,nond[N*2],u,w,z;
15 
16 void Add(int u,int w,int z)
17 {
18     edge[++tto].x=u,edge[tto].y=w,edge[tto].nxt=vis[z],vis[z]=tto;
19 }
20 
21 void add(int u,int w)
22 {
23     dis[++tot].x=u;
24     dis[tot].y=w;
25     dis[tot].nxt=st[u];
26     st[u]=tot;
27     nond[tot]=u;
28     dis[++tot].x=w;
29     dis[tot].y=u;
30     dis[tot].nxt=st[w];
31     st[w]=tot;
32     nond[tot]=w;
33 }
34 
35 int dfs(int now)
36 {
37     p[now]=num;
38     int maxn1=0;
39     for(int i=st[now]; i; i=dis[i].nxt)
40         if(p[dis[i].y]!=num)
41         {
42             int r=dfs(dis[i].y);
43             maxn=max(maxn,r+maxn1+1);
44             maxn1=max(maxn1,r+1);
45         }
46     return maxn1;
47 }
48 
49 int main()
50 {
51 //    freopen("walk.in","r",stdin);
52 //    freopen("walk.out","w",stdout);
53     scanf("%d",&n);
54     for(int i=1; i<n; i++)
55     {
56         scanf("%d%d%d",&u,&w,&z);
57         mx=max(mx,z);
58         Add(u,w,z);
59     }
60     for(int i=1; i<=mx; i++)
61     {
62         for(int j=i; j<=mx; j+=i)
63             for(int k=vis[j]; k; k=edge[k].nxt)
64                 add(edge[k].x,edge[k].y);
65         maxn=0;
66         num++;
67         for(int k=1; k<=tot; k++)
68             if(p[nond[k]]!=num) dfs(nond[k]);
69         for(int k=1; k<=tot; k++) st[nond[k]]=0;
70         tot=0;
71         ans[maxn]=i;
72     }
73     for(int i=n-1; i>0; i--) ans[i]=max(ans[i],ans[i+1]);
74     for(int i=1; i<=n; i++) printf("%d
",ans[i]);
75     return 0;
76 }

T3：

题目链接：https://www.luogu.org/problemnew/show/U30699

题意：

给定一个长度为n的序列，和初始位置，向左走的次数，

规定每走一步的花费为起始点的值和到达点的值的差的绝对值，

序列中每个点必须到达一次并且不能重复到达。

求出最小花费并输出最小花费。

若无法满足要求，则输出-1.

做的时候结合所给样例，考虑到了几种特殊情况，

正常可以满足要求的情况下，

所有向左的操作加起来一定会到达最左边的一点，

向右的操作最后会到达最右边的点，

所以当初始位置距离最左边的点的距离小于向左走的步数时，一定是不满足要求的，

此时输出“-1”。

同理，当初始位置距离最右边的点的距离小于向右走的步数（题目给出）时，也是不满足要求的，

此时也输出“-1”，结束。

另外一种比较好想的情况是：

当初始位置距离最左边的点的距离恰好等于向左走的步数L时，

这种情况下向左的操作就只能一次走一步，一步一步到达最左边的一点，

而向友也就一样了，此时的最小路径就是，

初始位置到达它左边每一个点的差的绝对值相加，

再加最左边位置与初始位置右边一点的差的绝对值，再一次向右加两点差的绝对值。

但这种情况是不多的。

正解：

假如某一次是从 i 向左跳，那么之前一定会从左侧跳到 i，

肯定会覆盖[i-1,i]的线段，然后从 i 向左跳走回头路，又会覆盖[i-1,i]一次，

最后因为一定要走到 n，所以在走完回头路后一定还会再向右跳回来，

所以至少经过三次[i-1,i]。也就至少有 L 条线段被覆盖至少 3 次。

这样我们就可以贪心的选取权值最小的 L 条线段计算作为答案了。

显然这种情况下 L 越小，答案越优。

不过起始和结束的位置不一定在两端，那假设结束的位置是 e，

根据对称性，不妨假设 s 在 e 的前面。显然 s 前面的线段和 e 后面的线段一定都至少经过两次，

而且存在方案能让 s 前和 e 后一共用掉 n-e+s-1 个 L，并且每条线段只经过两次。

这样不仅能减少[s,e]中间走 L 的次数，而且也让 s 和 e 两侧的花费尽量小。

中间的部分事实上和刚才讨论的从 1 开始，n 为终点的情况是完全一样的。

这样我们就可以直接枚举 e 来计算答案了，继而发现 e=i 和e=i+1 的情况只是有[i,i+1]这条线段覆盖次数限制的变化，

其他线段都没有影响。所以在枚举 e 的时候，我们用一个堆或者是队列来维护权值最小的若干条线段就好了。

ac代码：

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 using namespace std;
  6 
  7 typedef long long LL;
  8 typedef pair<int,int> mp;
  9 const LL inf = 1ll<<50;
 10 const int maxn = 200005;
 11 
 12 int n,l,s,pos[maxn];
 13 int x[maxn],ans1[maxn];
 14 int y[maxn],ans2[maxn];
 15 mp ord[maxn];
 16 bool tag[maxn];
 17 
 18 LL solve(int n,int l,int s,int x[],int ans[])
 19 {
 20     int cnt=0,tot=0;
 21     if (l<s)
 22     {
 23         for (int i=s-1; i>s-l; i--) ans[++cnt]=i;
 24         for (int i=1; i<=s-l; i++) if (i!=s) ans[++cnt]=i;
 25         for (int i=s+1; i<=n; i++) ans[++cnt]=i;
 26         return (LL)x[n]-x[1]+x[s]-x[1];
 27     }
 28     
 29     l-=s-1;
 30     if (l==n-s-1)
 31     {
 32         for (int i=s-1; i>=1; i--) ans[++cnt]=i;
 33         for (int i=n; i>s; i--) ans[++cnt]=i;
 34         return (LL)x[n]-x[1]+x[s]-x[1]+x[n]-x[s+1];
 35     }
 36     for (int i=s+1; i<n-1; i++) 
 37         ord[++tot]=mp(x[i+1]-x[i],i+1);
 38     sort(ord+1,ord+tot+1);
 39     for (int i=1; i<=tot; i++) 
 40         pos[ord[i].second]=i;
 41     LL minv=inf,sum=0;
 42     int e,j;
 43     for (int i=1; i<=l; i++) 
 44         sum+=ord[i].first;
 45     minv=sum*2;
 46     e=n;
 47     j=l;
 48     for (int i=n-1,p=l; i>=n-l; i--)
 49     {
 50         if (pos[i]<=p) sum-=ord[pos[i]].first;
 51         else sum-=ord[p--].first;
 52         while (p&&ord[p].second>=i) --p;
 53         if (sum*2+x[n]-x[i]<minv)
 54         {
 55             minv=sum*2+x[n]-x[i];
 56             e=i;
 57             j=p;
 58         }
 59     }
 60     memset(tag,false,sizeof tag);
 61     for (int i=s-1; i>=1; i--) 
 62         ans[++cnt]=i;
 63     for (int i=s+2; i<e; i++) 
 64         if(pos[i]<=j) tag[i]=true;
 65     for (int i=s+1; i<e; i++)
 66         if (!tag[i+1]) ans[++cnt]=i;
 67         else
 68         {
 69             int tmp=i+1;
 70             while (tag[tmp]) ++tmp;
 71             for (int j=tmp-1; j>i; j--) 
 72                 ans[++cnt]=j;
 73             ans[++cnt]=i;
 74             i=tmp-1;
 75         }
 76     for (int i=n; i>=e; i--) 
 77         ans[++cnt]=i;
 78     return (LL)x[n]-x[1]+x[s]-x[1]+minv;
 79 }
 80 int main()
 81 {
 82     //freopen("travel.in","r",stdin);
 83     //freopen("travel.out","w",stdout);
 84     scanf("%d %d %d",&n,&l,&s);
 85     for (int i=1; i<=n; i++) 
 86         scanf("%d",&x[i]);
 87     for (int i=1; i<=n; i++) 
 88         y[i]=-x[n-i+1];
 89     if (s!=1&&l==0)
 90     {
 91         puts("-1");
 92         return 0;
 93     }
 94     if (s!=n&&l==n-1)
 95     {
 96         puts("-1");
 97         return 0;
 98     }
 99     LL cost1=solve(n,l,s,x,ans1);
100     LL cost2=solve(n,n-1-l,n-s+1,y,ans2);
101     if (cost1<cost2)
102     {
103         printf("%lld
",cost1);
104         for (int j=1; j<n; j++)
105             printf("%d ",ans1[j]);
106     }
107     else
108     {
109         printf("%lld
",cost2);
110         for (int j=1; j<n; j++)
111             printf("%d ",n-ans2[j]+1);
112     }
113     return 0;
114 }

如果你不开心，那我就把右边这个帅傻子分享给你吧，
你看，他这么好看，跟个zz一样看着你，你还伤心吗？
真的！这照片盯上他五秒钟就想笑了。
一切都会过去的。
时间时间会给你答案2333