水题ing

T1：　

https://www.luogu.org/problemnew/show/P1724
幻想乡，东风谷早苗是以高达控闻名的高中生宅巫女。某一天，早苗终于入手了最新款的钢达姆模型。作为最新的钢达姆，当然有了与以往不同的功能了，那就是它能够自动行走，厉害吧（好吧，我自重）。
早苗的新模型可以按照输入的命令进行移动，命令包含’E’、’S’、’W’、’N’四种，分别对应四个不同的方向，依次为东、南、西、北。执行某个命令时，它会向着对应方向移动一个单位。作为新型机器人，
自然不会只单单执行一个命令，它可以执行命令串。对于输入的命令串，每一秒它会按照命令行动一次。而执行完命令串最后一个命令后，会自动从头开始循环。在0时刻时早苗将钢达姆放置在了(,)的位置，
并且输入了命令串。她想要知道T秒后钢达姆所在的位置坐标。

向东移动，坐标改变改变为(X+,Y);

向南移动，坐标改变改变为(X,Y-);

向西移动，坐标改变改变为(X-,Y);

向北移动，坐标改变改变为(X,Y+);

输入输出格式

输入格式：

第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令

第2行：一个正整数T

输出格式：

第1行：两个整数，表示T秒时，钢达姆的坐标

　　很简单的模拟，由于是循环的，所以只需要走一个完整的一次，还有后面剩下的一点就可以了

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<string>

 using namespace std;

 string s;

 int n;

 int x,y;

 int main()

 {

     freopen("robot.in","r",stdin);

     freopen("robot.out","w",stdout);

     cin>>s>>n;

     int len=s.length();

     for(int i=;i<len;++i)

     {

         if(s[i]=='N')y++;

         if(s[i]=='S')y--;

         if(s[i]=='E')x++;

         if(s[i]=='W')x--;

     }

     int a=n/len;

     x*=a,y*=a;

     n%=len;

     for(int i=;i<n;++i)

     {

         if(s[i]=='N')y++;

         if(s[i]=='S')y--;

         if(s[i]=='E')x++;

         if(s[i]=='W')x--;

     }

     printf("%d %d",x,y);

     fclose(stdin);fclose(stdout);

     return ;

 }

 /*

 NSWWNSNEEWN

 12

 */

T2：

题目描述    
　　在幻想乡，西行寺幽幽子是以贪吃闻名的亡灵。不过幽幽子可不是只会吃，至少她还管理着亡灵界。
　　话说在幽幽子居住的白玉楼有一颗常年不开花的樱树——西行妖。幽幽子决定去收集人间的春度，聚集起来让西行妖开花。
　　很快，作为幽幽子家园艺师的魂魄妖梦收集到了 M 个单位的春度。并且在这段时间里，幽幽子计算出要让西行妖开出一朵花需要 N 个单位的春度。

现在幽幽子想要知道，使用所有的春度，能够让西行妖开出多少朵花。

输入格式    第  行：一个正整数 M

第  行：一个正整数 N

N,M 的位数不超过L，L 的范围在题目后面给出

输出格式    第  行：一个整数ans，表示能开出花的朵数

输入样例    

输出样例

数据范围    对于 %的数据：L <= , 且 ans <= ,

对于 %的数据：L <= , 且 ans <= ,,,

　　裸的高精除，然而蒟蒻并不会写高精除，看到ans是int范围的，果断二分，后来才知道std也是这么写的，只不过人家还转换成二进制了什么的Orz。二分答案，变成高精乘低精，会好些很多。

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<string>

 #include<cstdlib>

 using namespace std;

 char s1[],s2[];

 int a1[],a2[];

 long long a3[];

 int ans;

 int tmp;

 int len1,len2;

 bool ok(int mid)

 {

     int len=;

     memset(a3,,sizeof(a3));

     a3[]=;//这里赋成0

     for(int i=;i<=len2;++i)

     {

         a3[i]+=1ll*a2[i]*mid;

         if(a3[i]>)

         {

             a3[i+]+=a3[i]/,a3[i]%=;

             if(i+>len)len=i+;//注意是len=i+1,而不是len++，一直都那么写的，才知道那样写是错的

             if(len>len1)return ;

         }

     }

     while(a3[len]>)

     {

         a3[len+]=a3[len]/,a3[len]%=,len++;

         if(len>len1)return ;

     }

     if(len<len1)return ;

     for(int i=len1;i>=;i--)

     {

         if(a1[i]>a3[i])return ;

         if(a1[i]<a3[i])return ;

     }

     return ;

 }

 int main()

 {

     freopen("spring.in","r",stdin);

     freopen("spring.out","w",stdout);

     scanf("%s",s1+),scanf("%s",s2+);

     len1=strlen(s1+),len2=strlen(s2+);

     tmp=len2;

     for(int i=;i<=len1;++i)a1[i]=s1[len1-i+]-'';

     for(int i=;i<=len2;++i)a2[i]=s2[len2-i+]-'';

     int l=,r=;

     while(l<=r)

     {

         int mid=(1ll*l+1ll*r)>>;

         if(ok(mid))ans=mid,l=mid+;

         else r=mid-;

     }

     printf("%d",ans);

     return ;

 }

 /*

 73861758

 12471

 */

T3:

题目描述    在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。
但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。
小河可以看作一列格子依次编号为  到 N，琪露诺只能从编号小的格子移动到编号大的格子。
而且琪露诺按照一种特殊的方式进行移动，当她在格子 i 时，她只会移动到 i+L 到 i+R 中的一格。
你问为什么她这么移动，这还不简单，因为她是笨蛋啊。每一个格子都有一个冰冻指数 A[i]，编号为  的格子冰冻指数为 。
当琪露诺停留在那一格时就可以得到那一格的冰冻指数 A[i]。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。
但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。开始时，琪露诺在编号  的格子上，只要她下一步的位置编号大于 N 就算到达对岸。

输入格式    第  行： 个正整数 N, L, R

第  行：N+ 个整数，第 i 个数表示编号为 i- 的格子的冰冻指数 A[i-]

输出格式    第  行：一个整数，表示最大冰冻指数。保证不超过 ^-

第  行：空格分开的若干个整数，表示琪露诺前进的路线，最后输出- 表示到达对岸

输入样例

     -

输出样例

  -

数据范围    对于 %的数据：N <= ,

对于 %的数据：N <= ,

对于所有数据 -, <= A[i] <= , 且  <= L <= R <= N

注意    此题采用 Special Judge

　　洛谷有一道这题的弱化版，就是不用输出路径，犹记得某位大佬说过，输出路径就是毒瘤啊，其实也还好，只是一开始并没有做出来，后来看了眼题解（捂脸），看到说用线段树或堆来维护最大值，恍然大悟（其实是又进一步知道了自己很弱），就是用线段树维护最大值就行了，但是由于需要的是谁去转移谁，所以在线段树里把最大值换成下标的形式来存储，然后每一次按着下标找相应的值就行了，输出就递归一下，和花店橱窗一样的qwq

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 const int maxn=;

 template<typename T>void read(T &a)

 {

     T x=,f=;char ch=getchar();

     while(!isdigit(ch))

     {

         if(ch=='-')f=;ch=getchar();

     }

     while(isdigit(ch))

     {

         x=(x<<)+(x<<)+ch-'';ch=getchar();

     }

     a=f?x:-x;

 }

 int n,l,r;

 int a[maxn];

 int f[maxn];

 int pre[maxn];

 int tree[maxn<<];

 int query(int now,int l,int r,int ql,int qr)

 {

     if(ql<=l&&qr>=r)

     {

         return tree[now];

     }

     int mid=(l+r)>>;

     if(qr<=mid)return query(now<<,l,mid,ql,qr);

     else if(ql>mid)return query(now<<|,mid+,r,ql,qr);

     else {

         int t1=query(now<<,l,mid,ql,qr),t2=query(now<<|,mid+,r,ql,qr);

         return f[t1]>f[t2]?t1:t2;

     }

 }

 void change(int now,int l,int r,int x)

 {

     if(l==r&&r==x)

     {

         tree[now]=x;return;

     }

     int mid=(l+r)>>;

     if(x<=mid)change(now<<,l,mid,x);

     else change(now<<|,mid+,r,x);

     tree[now]= f[tree[now<<]]>f[tree[now<<|]]?(tree[now<<]):(tree[now<<|]);

 }

 void out(int x)

 {

     if(!pre[x])

     {

         printf("0 ");return;

     }

     out(pre[x]);

     if(x>=n)printf("-1");

     else printf("%d ",x);

 }

 int main()

 {

     freopen("iceroad.in","r",stdin);

     freopen("iceroad.out","w",stdout);

     read(n),read(l),read(r);

     for(int i=;i<=n;++i)read(a[i]);

     memset(tree,-,sizeof(tree));

     memset(f,-,sizeof(f));

     f[]=;

     change(,,n+max(l,r),);

     for(int i=l;i<=n+max(l,r);++i)

     {

         int t=query(,,n+max(l,r),max(,i-r),i-l);

         pre[i]=t,f[i]=f[t]+a[i];

         change(,,n+max(l,r),i);

     }

     int ans=-,x;

     for(int i=n;i<=n+max(l,r);++i)if(f[i]>ans)ans=f[i],x=i;

     printf("%d\n",ans);

     out(x);

     fclose(stdin);fclose(stdout);

     return ;

 }

 /*

 5 2 3

 0 12 3 11 7 -2

 */

https://www.luogu.org/problemnew/show/P1726
题目描述

在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。
人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。
当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。
现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,,4和2,,6这两个最大连通区域时，输出的是1,,。

输入输出格式

输入格式：

第1行：两个正整数N,M

第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。

输出格式：

第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。

第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。

　　这题。。。。仔细看了一遍题的人应该都能看出来是tarjan，但是本弱就是那种没有好好读题的人QAQ。裸的求最大的强连通分量，并且把属于这个强连通分量的点输出。

代码：

 #include<iostream>

 #include<cstdio>

 using namespace std;//

 const int maxn=,maxm=;

 int n,m;

 int x,y,t;

 struct zhw{

     int to,last;

 }tu[maxm<<];

 int tot,head[maxn];

 void add(int x,int y)

 {

     tot++,tu[tot].to=y,tu[tot].last=head[x],head[x]=tot;

 }

 int tim,low[maxn],dfn[maxn];

 int stack[maxn],top,belong[maxn];

 int ans;

 bool vis[maxn];

 int cnt[maxn];

 int js;

 void tarjan(int x)

 {

     vis[x]=,stack[++top]=x;

     low[x]=dfn[x]=++tim;

     for(int i=head[x];i;i=tu[i].last)

     {

         if(!dfn[tu[i].to])tarjan(tu[i].to),low[x]=min(low[x],low[tu[i].to]);

         else if(vis[tu[i].to])low[x]=min(low[x],low[tu[i].to]);

     }

     int p=-;

     if(low[x]==dfn[x])

     {

         js++;

         while(p!=x)

         {

             p=stack[top],top--;

             cnt[js]++,belong[p]=js;

             vis[p]=;//没有写导致挂掉

         }

         if(cnt[js]>cnt[ans])ans=js;

     }

 }

 int main()

 {

     freopen("classroom.in","r",stdin);

     freopen("classroom.out","w",stdout);

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;++i)

     {

         scanf("%d%d%d",&x,&y,&t);

         add(x,y);

         if(t==)add(y,x);

     }

     for(int i=;i<=n;++i)

         if(!dfn[i])tarjan(i);

     printf("%d\n",cnt[ans]);

     for(int i=;i<=n;++i)

         if(belong[i]==ans)printf("%d ",i);

     return ;

 }

 /*

 5 5

 1 2 1

 1 3 2

 2 4 2

 5 1 2

 3 5 1

 */

　　以上图片均来自cogs，qwq

巴特西

水题ing

最新文章

热门文章