T1：
https://www.luogu.org/problemnew/show/P1724
幻想乡，东风谷早苗是以高达控闻名的高中生宅巫女。某一天，早苗终于入手了最新款的钢达姆模型。作为最新的钢达姆，当然有了与以往不同的功能了，那就是它能够自动行走，厉害吧（好吧，我自重）。
早苗的新模型可以按照输入的命令进行移动，命令包含’E’、’S’、’W’、’N’四种，分别对应四个不同的方向，依次为东、南、西、北。执行某个命令时，它会向着对应方向移动一个单位。作为新型机器人，
自然不会只单单执行一个命令，它可以执行命令串。对于输入的命令串，每一秒它会按照命令行动一次。而执行完命令串最后一个命令后，会自动从头开始循环。在0时刻时早苗将钢达姆放置在了(0,0)的位置，
并且输入了命令串。她想要知道T秒后钢达姆所在的位置坐标。 向东移动，坐标改变改变为(X+1,Y); 向南移动，坐标改变改变为(X,Y-1); 向西移动，坐标改变改变为(X-1,Y); 向北移动，坐标改变改变为(X,Y+1); 输入输出格式 输入格式： 第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令 第2行：一个正整数T 输出格式： 第1行：两个整数，表示T秒时，钢达姆的坐标
很简单的模拟，由于是循环的，所以只需要走一个完整的一次，还有后面剩下的一点就可以了
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<string> 5 using namespace std; 6 string s; 7 int n; 8 int x,y; 9 int main() 10 { 11 freopen("robot.in","r",stdin); 12 freopen("robot.out","w",stdout); 13 cin>>s>>n; 14 int len=s.length(); 15 for(int i=0;i<len;++i) 16 { 17 if(s[i]=='N')y++; 18 if(s[i]=='S')y--; 19 if(s[i]=='E')x++; 20 if(s[i]=='W')x--; 21 } 22 int a=n/len; 23 x*=a,y*=a; 24 n%=len; 25 for(int i=0;i<n;++i) 26 { 27 if(s[i]=='N')y++; 28 if(s[i]=='S')y--; 29 if(s[i]=='E')x++; 30 if(s[i]=='W')x--; 31 } 32 printf("%d %d",x,y); 33 fclose(stdin);fclose(stdout); 34 return 0; 35 } 36 /* 37 NSWWNSNEEWN 38 12 39 */
T2：
题目描述
在幻想乡，西行寺幽幽子是以贪吃闻名的亡灵。不过幽幽子可不是只会吃，至少她还管理着亡灵界。
话说在幽幽子居住的白玉楼有一颗常年不开花的樱树——西行妖。幽幽子决定去收集人间的春度，聚集起来让西行妖开花。
很快，作为幽幽子家园艺师的魂魄妖梦收集到了 M 个单位的春度。并且在这段时间里，幽幽子计算出要让西行妖开出一朵花需要 N 个单位的春度。 现在幽幽子想要知道，使用所有的春度，能够让西行妖开出多少朵花。 输入格式 第 1 行：一个正整数 M 第 2 行：一个正整数 N N,M 的位数不超过L，L 的范围在题目后面给出 输出格式 第 1 行：一个整数ans，表示能开出花的朵数 输入样例 73861758 12471 输出样例 5922 数据范围 对于 60%的数据：L <= 2,000 且 ans <= 2,000 对于 100%的数据：L <= 20,000 且 ans <= 2,000,000,000
裸的高精除，然而蒟蒻并不会写高精除，看到ans是int范围的，果断二分，后来才知道std也是这么写的，只不过人家还转换成二进制了什么的Orz。二分答案，变成高精乘低精，会好些很多。
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<string> 5 #include<cstdlib> 6 using namespace std; 7 char s1[20005],s2[20005]; 8 int a1[20005],a2[20005]; 9 long long a3[20005]; 10 int ans; 11 int tmp; 12 int len1,len2; 13 bool ok(int mid) 14 { 15 int len=1; 16 memset(a3,0,sizeof(a3)); 17 a3[1]=0;//这里赋成0 18 for(int i=1;i<=len2;++i) 19 { 20 a3[i]+=1ll*a2[i]*mid; 21 if(a3[i]>9) 22 { 23 a3[i+1]+=a3[i]/10,a3[i]%=10; 24 if(i+1>len)len=i+1;//注意是len=i+1,而不是len++，一直都那么写的，才知道那样写是错的 25 if(len>len1)return 0; 26 } 27 } 28 while(a3[len]>9) 29 { 30 a3[len+1]=a3[len]/10,a3[len]%=10,len++; 31 if(len>len1)return 0; 32 } 33 if(len<len1)return 1; 34 for(int i=len1;i>=1;i--) 35 { 36 if(a1[i]>a3[i])return 1; 37 if(a1[i]<a3[i])return 0; 38 } 39 return 1; 40 } 41 int main() 42 { 43 freopen("spring.in","r",stdin); 44 freopen("spring.out","w",stdout); 45 scanf("%s",s1+1),scanf("%s",s2+1); 46 len1=strlen(s1+1),len2=strlen(s2+1); 47 tmp=len2; 48 for(int i=1;i<=len1;++i)a1[i]=s1[len1-i+1]-'0'; 49 for(int i=1;i<=len2;++i)a2[i]=s2[len2-i+1]-'0'; 50 int l=0,r=2000000000; 51 while(l<=r) 52 { 53 int mid=(1ll*l+1ll*r)>>1; 54 if(ok(mid))ans=mid,l=mid+1; 55 else r=mid-1; 56 } 57 printf("%d",ans); 58 return 0; 59 } 60 /* 61 73861758 62 12471 63 */
T3:
题目描述 在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。
但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。
小河可以看作一列格子依次编号为 0 到 N，琪露诺只能从编号小的格子移动到编号大的格子。
而且琪露诺按照一种特殊的方式进行移动，当她在格子 i 时，她只会移动到 i+L 到 i+R 中的一格。
你问为什么她这么移动，这还不简单，因为她是笨蛋啊。每一个格子都有一个冰冻指数 A[i]，编号为 0 的格子冰冻指数为 0。
当琪露诺停留在那一格时就可以得到那一格的冰冻指数 A[i]。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。
但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。开始时，琪露诺在编号 0 的格子上，只要她下一步的位置编号大于 N 就算到达对岸。 输入格式 第 1 行：3 个正整数 N, L, R 第 2 行：N+1 个整数，第 i 个数表示编号为 i-1 的格子的冰冻指数 A[i-1] 输出格式 第 1 行：一个整数，表示最大冰冻指数。保证不超过 2^31-1 第 2 行：空格分开的若干个整数，表示琪露诺前进的路线，最后输出-1 表示到达对岸 输入样例 5 2 3 0 12 3 11 7 -2 输出样例 11 0 3 -1 数据范围 对于 60%的数据：N <= 10,000 对于 100%的数据：N <= 200,000 对于所有数据 -1,000 <= A[i] <= 1,000 且 1 <= L <= R <= N 注意 此题采用 Special Judge
洛谷有一道这题的弱化版，就是不用输出路径，犹记得某位大佬说过，输出路径就是毒瘤啊，其实也还好，只是一开始并没有做出来，后来看了眼题解（捂脸），看到说用线段树或堆来维护最大值，恍然大悟（其实是又进一步知道了自己很弱），就是用线段树维护最大值就行了，但是由于需要的是谁去转移谁，所以在线段树里把最大值换成下标的形式来存储，然后每一次按着下标找相应的值就行了，输出就递归一下，和花店橱窗一样的qwq
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 const int maxn=405005; 6 template<typename T>void read(T &a) 7 { 8 T x=0,f=1;char ch=getchar(); 9 while(!isdigit(ch)) 10 { 11 if(ch=='-')f=0;ch=getchar(); 12 } 13 while(isdigit(ch)) 14 { 15 x=(x<<1)+(x<<3)+ch-'0';ch=getchar(); 16 } 17 a=f?x:-x; 18 } 19 int n,l,r; 20 int a[maxn]; 21 int f[maxn]; 22 int pre[maxn]; 23 int tree[maxn<<2]; 24 int query(int now,int l,int r,int ql,int qr) 25 { 26 if(ql<=l&&qr>=r) 27 { 28 return tree[now]; 29 } 30 int mid=(l+r)>>1; 31 if(qr<=mid)return query(now<<1,l,mid,ql,qr); 32 else if(ql>mid)return query(now<<1|1,mid+1,r,ql,qr); 33 else { 34 int t1=query(now<<1,l,mid,ql,qr),t2=query(now<<1|1,mid+1,r,ql,qr); 35 return f[t1]>f[t2]?t1:t2; 36 } 37 } 38 void change(int now,int l,int r,int x) 39 { 40 if(l==r&&r==x) 41 { 42 tree[now]=x;return; 43 } 44 int mid=(l+r)>>1; 45 if(x<=mid)change(now<<1,l,mid,x); 46 else change(now<<1|1,mid+1,r,x); 47 tree[now]= f[tree[now<<1]]>f[tree[now<<1|1]]?(tree[now<<1]):(tree[now<<1|1]); 48 } 49 void out(int x) 50 { 51 if(!pre[x]) 52 { 53 printf("0 ");return; 54 } 55 out(pre[x]); 56 if(x>=n)printf("-1"); 57 else printf("%d ",x); 58 } 59 int main() 60 { 61 freopen("iceroad.in","r",stdin); 62 freopen("iceroad.out","w",stdout); 63 read(n),read(l),read(r); 64 for(int i=0;i<=n;++i)read(a[i]); 65 memset(tree,-1,sizeof(tree)); 66 memset(f,-1,sizeof(f)); 67 f[0]=0; 68 change(1,0,n+max(l,r),0); 69 for(int i=l;i<=n+max(l,r);++i) 70 { 71 int t=query(1,0,n+max(l,r),max(0,i-r),i-l); 72 pre[i]=t,f[i]=f[t]+a[i]; 73 change(1,0,n+max(l,r),i); 74 } 75 int ans=-1,x; 76 for(int i=n;i<=n+max(l,r);++i)if(f[i]>ans)ans=f[i],x=i; 77 printf("%d ",ans); 78 out(x); 79 fclose(stdin);fclose(stdout); 80 return 0; 81 } 82 /* 83 5 2 3 84 0 12 3 11 7 -2 85 */
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,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。 输入输出格式 输入格式： 第1行：两个正整数N,M 第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。 输出格式： 第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。 第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。
这题。。。。仔细看了一遍题的人应该都能看出来是tarjan，但是本弱就是那种没有好好读题的人QAQ。裸的求最大的强连通分量，并且把属于这个强连通分量的点输出。
代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std;// 4 const int maxn=5005,maxm=50005; 5 int n,m; 6 int x,y,t; 7 struct zhw{ 8 int to,last; 9 }tu[maxm<<1]; 10 int tot,head[maxn]; 11 void add(int x,int y) 12 { 13 tot++,tu[tot].to=y,tu[tot].last=head[x],head[x]=tot; 14 } 15 int tim,low[maxn],dfn[maxn]; 16 int stack[maxn],top,belong[maxn]; 17 int ans; 18 bool vis[maxn]; 19 int cnt[maxn]; 20 int js; 21 void tarjan(int x) 22 { 23 vis[x]=1,stack[++top]=x; 24 low[x]=dfn[x]=++tim; 25 for(int i=head[x];i;i=tu[i].last) 26 { 27 if(!dfn[tu[i].to])tarjan(tu[i].to),low[x]=min(low[x],low[tu[i].to]); 28 else if(vis[tu[i].to])low[x]=min(low[x],low[tu[i].to]); 29 } 30 int p=-1; 31 if(low[x]==dfn[x]) 32 { 33 js++; 34 while(p!=x) 35 { 36 p=stack[top],top--; 37 cnt[js]++,belong[p]=js; 38 vis[p]=0;//没有写导致挂掉 39 } 40 if(cnt[js]>cnt[ans])ans=js; 41 } 42 } 43 int main() 44 { 45 freopen("classroom.in","r",stdin); 46 freopen("classroom.out","w",stdout); 47 scanf("%d%d",&n,&m); 48 for(int i=1;i<=m;++i) 49 { 50 scanf("%d%d%d",&x,&y,&t); 51 add(x,y); 52 if(t==2)add(y,x); 53 } 54 for(int i=1;i<=n;++i) 55 if(!dfn[i])tarjan(i); 56 printf("%d ",cnt[ans]); 57 for(int i=1;i<=n;++i) 58 if(belong[i]==ans)printf("%d ",i); 59 return 0; 60 } 61 /* 62 5 5 63 1 2 1 64 1 3 2 65 2 4 2 66 5 1 2 67 3 5 1 68 */
以上图片均来自cogs，qwq