本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-25 19:45:46

思路

考虑枚举每一组 $(a,b,c)$ ，去寻找 $d$ 。

具体实现上将每一组 $(a,b,c)$ 根据 $(a,b)$ 储存在集合中，之后枚举每一组 $a,b,c$ 根据 $(a,b)$ 、 $(a,c)$ 、 $(b,c)$ 、 可以找到 $d$ 。

代码

\/\/ Problem: T500879 【MX-J3-T3】Tuple
\/\/ Contest: Luogu
\/\/ URL: https:\/\/www.luogu.com.cn\/problem\/T500879?contestId=193566
\/\/ Memory Limit: 512 MB
\/\/ Time Limit: 1000 ms
\/\/ 
\/\/ Powered by CP Editor (https:\/\/cpeditor.org)

#include<bits\/stdc++.h>

#define zibenlun "\n========================================================\n"
#define int long long
#define int_128 __int128
#define debug cout<<1;
#define lowbit(x) (x&(-x))
#define faster ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
inline int read() {
	int s=0,flag=0;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();
	if(ch=='-') {
		flag=1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		s=s*10+(ch^48);
		ch=getchar();
	}
	if(flag) return -s;
	return s;
}
inline void write(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x\/10);
	putchar(x%10+'0');
}
unordered_map<int,int> mp[300005];
unordered_set<int> s[300005];
int n,m;
struct nd{
	int a,b,c;
}a[300005];
int ans;
int cnt;
signed main() {
\/\/	freopen(".in","r",stdin);
\/\/	freopen(".out","w",stdout);
	faster
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].a>>a[i].b>>a[i].c;
		if(mp[a[i].a][a[i].b]==0){
			mp[a[i].a][a[i].b]=++cnt;
		}
		s[mp[a[i].a][a[i].b]].insert(a[i].c);
	}
	for(int i=1;i<=m;i++){
		if(a[i].c==n) continue;
		if(s[mp[a[i].b][a[i].c]].size()==0||s[mp[a[i].a][a[i].c]].size()==0) continue;
		int minn=min(min(s[mp[a[i].b][a[i].c]].size(),s[mp[a[i].a][a[i].b]].size()),s[mp[a[i].a][a[i].c]].size());
		if(s[mp[a[i].a][a[i].b]].size()==minn)
			for(auto j:s[mp[a[i].a][a[i].b]]){
				if(j==a[i].c) continue;
				if(s[mp[a[i].b][a[i].c]].count(j)&&s[mp[a[i].a][a[i].c]].count(j)){
					ans++;
				}
			}
		else if(s[mp[a[i].b][a[i].c]].size()==minn)
			for(auto j:s[mp[a[i].b][a[i].c]]){
				if(s[mp[a[i].a][a[i].b]].count(j)&&s[mp[a[i].a][a[i].c]].count(j)){
					ans++;
				}
			}
		else 
			for(auto j:s[mp[a[i].a][a[i].c]]){
				if(s[mp[a[i].a][a[i].b]].count(j)&&s[mp[a[i].b][a[i].c]].count(j)){
					ans++;
				}
			}
	}
	cout<<ans;
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-01 15:48:29

思路

首先思考 Takahashi 如何让自己走过的路径最小。根据题意，一定要从 1 号点出发并回到 1 号点，所以每一个点到 1 号点之间的边一定是要经过两次的。

知道了计算经过所有点的路径长度的方法之后，就可以根据其特点发现，当选取部分点的时候，选子节点一定比选择他的祖先更优。因为选取子节点后，同样会经过其祖先，所以说选择一个点就相当于选择了其祖先。现在我们只需要统计所有的叶子的权值（到达此处的路径长度和）。此时我们会发现有多个儿子的点会导致路径长度的重复计算，我们需要将有多个儿子的节点的权值转移给它其中的一个儿子。因为选取点的时候是按照路径最长的方式选取，所以每一次都是要选取能使路径增加最长的点，所以我们选择将每个点的权值传递给他的重儿子。之后统计所有的叶子的权值，输出即可。

代码

#include<bits\/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
struct nd{int y,z;};
int s[N],dp[N],n,ans;
priority_queue<int> q;
vector<nd> v[N];
void dfs(int x,int fa){\/\/找重儿子
	int maxx=0;
	for(auto i:v[x]){
		if(i.y==fa) continue;
		dp[i.y]=i.z;
		dfs(i.y,x);
		if(dp[i.y]>maxx)maxx=dp[i.y],s[x]=i.y;
	}
	dp[x]+=maxx;
}
void dfss(int x,int fa){\/\/计算所有点的权值
	for(auto i:v[x]){
		if(i.y==fa) continue;
		if(s[x]==i.y)dp[i.y]=dp[x]+i.z;
		else dp[i.y]=i.z;
        \/\/转移给重儿子
		dfss(i.y,x);
	}if(v[x].size()==1&&fa!=0)q.push(dp[x]);
    \/\/存下叶子
}
signed main() {
	cin>>n;
	for(int i=1,x,y,z;i<n;i++) {
		cin>>x>>y>>z;
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	dfs(1,0);dp[1]=0;dfss(1,0);
    \/\/dp数组用了两次
    \/\/在dfs中用于统计重儿子
    \/\/在dfss中用于存储当前点的权值
	for(int i=1;i<=n;i++){
		if(q.size()) ans+=q.top()*2,q.pop();
        \/\/在所有为选取的叶子中选择最大的
        \/\/选完所有的叶子后，其他的点不在会对答案产生贡献
		cout<<ans<<"\n";
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-02 08:44:57

思路

每一个硬币一定是从比它横纵坐标都小的硬币上转移过来，我们将所有硬币先按横坐标排序，再按纵坐标排序，枚举每一个硬币，用树状数组维护，并标记每一个硬币从哪一个硬币转移过来。

代码

#include<bits\/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
#define faster ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
int n,m,q;
int c[200005];
int ans;
struct nd{
	int x,y;
}a[200005];
int dp[200005];
int v[200005];
int pos[200005];
bool cmp(nd x,nd y){
	if(x.x==y.x) return x.y<y.y;
	return x.x<y.x;
}
void add(int x,int e,int id){
	for(int i=x;i<=m;i+=lowbit(i)){
		if(e>=c[i]) c[i]=e,pos[i]=id;
	}
}
int ask(int x){
	int sum=0,ps=0;
	for(int i=x;i;i-=lowbit(i)){
		if(c[i]>=sum){
			sum=c[i];
			ps=pos[i];
		}
	}
	return ps;
}
signed main() {
	faster
	cin>>n>>m>>q;
	for(int i=1;i<=q;i++){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+1+q,cmp);
	a[0].x=1;
	a[0].y=1;
	a[q+1].x=n;
	a[q+1].y=m;
	for(int i=1;i<=q;i++){
		int x=ask(a[i].y);
		dp[i]=dp[x]+1;
		v[i]=x;
		add(a[i].y,dp[i],i);
	}
	int k=ask(m);
	\/\/ cout<<x;
	cout<<dp[k];
	cout<<"\n";
	int x=1,y=1;
	stack<int> s;
	s.push(q+1);
	int pos=k;
	while(pos!=0){
		s.push(pos);
		pos=v[pos];
	}
	while(s.size()){
		int i=s.top();
		s.pop();
		while(x<a[i].x) {
			cout<<"D";
			x++;
		}
		while(y<a[i].y){
			cout<<"R";
			y++;
		}
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-02 08:54:09

思路

看到 $n$ 的范围很小，所以能够用 Floyd 跑出所有点之间的最短路。看到每一次询问，我们将经过 $k$ 条边转化为依次经过 $k+k$ 个点，当然在一条边上的点必须相邻，所以可以将所有的边全排列，并枚举先经过每一条边上的哪一个点，求一个最小值即可。

代码

#include<bits\/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
#define faster ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
struct nd{
	int x,y,z;
}a[200005];
int b[105];
int dp[505][505];
int n,m,q,k;
signed main() {
	faster
	cin>>n>>m;memset(dp,0x3f,sizeof dp);
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[i]={x,y,z};
		dp[x][y]=min(dp[x][y],z);
		dp[y][x]=min(dp[y][x],z);
	}
	for(int i=1;i<=n;i++){
		dp[i][i]=0;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>k;
		int ans=1e18;
		for(int j=1;j<=k;j++){
			cin>>b[j];
		}sort(b+1,b+1+k);
	    do  {
	    	for(int u=0;u<(1<<k);u++){
	    		\/\/ cout<<1;
	    		int vis[10]={0},o=u;
	    		for(int j=1;j<=k;j++){
	    			if(o&1) vis[j]=1;
	    			o>>=1;
	    		}
	    		int pos=1,sum=0;
	    		for(int j=1;j<=k;j++){
	    			if(vis[j]==0){
	    				sum+=dp[pos][a[b[j]].x]+a[b[j]].z;pos=a[b[j]].y;
	    			}
	    			else {
	    				sum+=dp[pos][a[b[j]].y]+a[b[j]].z;pos=a[b[j]].x;
	    			}
	    		}
	    		ans=min(ans,sum+dp[pos][n]);
	    	}
	    }while(next_permutation(b+1,b+1+k));  
		cout<<ans<<"\n";
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-10 17:13:57

来一篇线段树题解吧

首先考虑简化问题，看到每一个物品的原本折扣，很显然可以把它当作每一个物品本来就有一个优惠券，所以问题就变成了给所有物品更新优惠券。

思考怎么更新优惠券，显然可以想到，对于每一个优惠券，如果它更新的物品原本的优惠越少，那么这张优惠券的贡献就越大。所以就可以每一次找出能更新的里面原本优惠最小的即可。更新的时候按照 $w$ 从大到小开始。实现这个操作可以通过把物品按照 $a$ 排序，这样每一次查询的范围就是一段后缀。只需要查后缀最小值再修改就可以了。

#include<bits\/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
struct nd{int a,b,c;}a[N];
struct {int l,r,minn;}c[N<<2];
int n,m,k[N],ans;
struct node{int w,v;}t[N];
bool cmpp(node x,node y){return x.w>y.w;}
bool cmp(nd x,nd y){return x.a<y.a;}
void pushup(int pos){
	if(a[c[pos<<1].minn].c<a[c[pos<<1|1].minn].c)c[pos].minn=c[pos<<1].minn;
	else c[pos].minn=c[pos<<1|1].minn;
}
void build(int pos,int l,int r){
	c[pos].l=l,c[pos].r=r;
	if(l==r){
		c[pos].minn=l;
		return ;
	}
	build(pos<<1,l,(l+r)\/2);
	build(pos<<1|1,(l+r)\/2+1,r);
	pushup(pos);
}
void change(int pos,int x,int v){
	if(c[pos].l>x||c[pos].r<x) return ;
	if(c[pos].l==x&&c[pos].r==x){
		a[x].c=v;
		return ;
	}
	change(pos<<1,x,v);
	change(pos<<1|1,x,v);
	pushup(pos);
}
int ask(int pos,int l,int r){
	if(c[pos].l>r||c[pos].r<l) return 0;
	if(c[pos].l>=l&&c[pos].r<=r)return c[pos].minn;
	int x=ask(pos<<1,l,r),y=ask(pos<<1|1,l,r);
	if(a[x].c<a[y].c) return x;
	else return y;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].a>>a[i].b;
		a[i].c=a[i].a-a[i].b;
	}
	for(int i=1;i<=m;i++) cin>>t[i].w>>t[i].v;
	a[0].c=1e18;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++) k[i]=a[i].a;
	sort(t+1,t+1+m,cmpp);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int x=ask(1,lower_bound(k+1,k+1+n,t[i].w)-k,n);
		if(a[x].c<t[i].v) change(1,x,t[i].v);
	}
	for(int i=1;i<=n;i++)ans+=a[i].a-a[i].c;cout<<ans;
	return 0;
}

自认为码风良好。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-14 10:31:45

不同的分块思路

预处理

需要预处理每一个点到父亲的边权，记录下来，把他变成点权，便于维护。

同时把所有点按照层数储存

分块

从上到下按照层数大小分块。对于每一个点处理出这一个点不断向上跳到最近的和它所属块的编号不同的点是哪一个，以及他们间路径的最大值。

修改

直接改点权即可。改完点权把同属同一个块的子节点的信息都更新。因为同属一个块，所以他们最终跳到的都是同一个点，修改的点之上的路径都是同时经过的。

查询

类似于 $LCA$ 的实现，我们可以先找到他们的 $LCA$ ,然后开始往上跳，只要不处于同一个块，就可以整个块跳，不然直接暴力跳。暴力跳的次数和整块跳的次数都是小于等于 $\sqrt n$ 次。

代码

#include<bits\/stdc++.h>
using namespace std;
const int N=1e5+5,len=300;
vector<int> v_d[N];
struct {int x,y,z;}c[N];
struct {int fa,maxx;}to_next[N];
int n,to_fa[N],f[N][25],d[N],pos[N];
vector<int> v[N];
void dfs(int x,int fa){
	d[x]=d[fa]+1;
	f[x][0]=fa;
    \/\/LCA
	for(int i=1;i<=20&&f[x][i-1]!=0;i++) f[x][i]=f[f[x][i-1]][i-1];
	v_d[d[x]].push_back(x);\/\/按照层数储存，便于分块
	for(int i=0;i<v[x].size();i++) if(v[x][i]!=fa) dfs(v[x][i],x);
}
int LCA(int x,int y){
	if(d[x]<d[y]) swap(x,y);
	for(int i=20;i>=0;i--)if(d[f[x][i]]>=d[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
\/\/ 处理 x 到它祖先里面最近的块不同的点之间的最大值
void solve(int x){
	if(x==1) return ;
	int fa=x,maxx=0;
	while(pos[fa]==pos[x])maxx=max(maxx,to_fa[fa]),fa=f[fa][0];
	to_next[x].fa=fa;\/\/记录整块会跳到哪一个点
	to_next[x].maxx=maxx;\/\/记录路径上的最大值
}
int get_max(int x,int y){
	int fa=LCA(x,y),ans=0;
	while(pos[x]!=pos[fa])ans=max(ans,to_next[x].maxx),x=to_next[x].fa;
	while(x!=fa)ans=max(ans,to_fa[x]),x=f[x][0];
    \/\/让 x 跳到 x,y 的最近公共祖先
	while(pos[y]!=pos[fa])ans=max(ans,to_next[y].maxx),y=to_next[y].fa;
	while(y!=fa)ans=max(ans,to_fa[y]),y=f[y][0];
	return ans;
}
bool vis[N];
\/\/ 快速更新同一个块里面的信息
void reset(int x){
    solve(x);
    \/\/先把当前点更新好，然后把他的子节点中和他在同一块里的更新
    \/\/因为最多有 len 个点，所以这个操作的时间复杂度是根号的
    queue<pair<int,int>> q;
    q.push({x,to_next[x].maxx});
    while(q.size()){
        int xx=q.front().first,z=q.front().second;
        vis[xx]=1;
        q.pop();
        for(int j=0;j<v[xx].size();j++){
            int i=v[xx][j];
            if(d[i]<d[xx]) continue;
            if(pos[i]==pos[x]){
                to_next[i].maxx=max(z,to_fa[i]);
                to_next[i].fa=to_next[x].fa;
                q.push(make_pair(i,to_next[i].maxx));
            }
        }
    }
}
signed main(){
	cin.tie(0)->sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>c[i].x>>c[i].y>>c[i].z;
		v[c[i].x].push_back(c[i].y);
		v[c[i].y].push_back(c[i].x);
	}
	dfs(1,0);
	int cnt=len-1,point=1;
	for(int i=1;i<=n;i++){
        \/\/记录每一个点向父亲连边的边权。
		if(d[c[i].x]<d[c[i].y]) to_fa[c[i].y]=c[i].z;
		else to_fa[c[i].x]=c[i].z;
        \/\/把每一个点放到块上
		for(int j=0;j<v_d[i].size();j++){
            cnt++;
			pos[v_d[i][j]]=point;
            if(cnt>=len) cnt=0,point++;
		}
	}
    \/\/初始化每一个点整块向上跳一次的终点和之间的最大值
	for(int k=2;k<=n;k++)
        for(int i=0;i<v_d[k].size();i++) 
            if(!vis[v_d[k][i]]) 
                reset(v_d[k][i]);
	string s;
	while(cin>>s){
		if(s=="DONE") return 0;
		int x,y,k;
		if(s=="CHANGE") {
			cin>>k>>x;
			c[k].z=x;
            \/\/更新边权
			if(d[c[k].x]<d[c[k].y]) to_fa[c[k].y]=c[k].z;
			else to_fa[c[k].x]=c[k].z;
            \/\/更新整块跳的最大值
			if(d[c[k].x]<d[c[k].y]) reset(c[k].y);
			else reset(c[k].x);
		}
		else {
			cin>>x>>y;
			cout<<get_max(x,y)<<"\n";
		}
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-19 08:19:24

怎么队友都写了。

第一次打ICPC，队友是KSCD_和Iceturky。

开场先看了G，之后跟榜写了 N ,和Iceturky写重了。然后想了一下L，没什么思路，去看了C，发现排序搞一下就行。写完看到Iceturky L WA 了，看了看他的思路，似乎很正确，就用他的思路写了个时间复杂度稍高一些的。之后接着想G，想了很久也没有思路，Iceturky后来切了。看到榜上有人切K就去写K。一看到K的图就有中邪恶的想法，就先写了个带路径的dp让他输出了路径，发现一开始一定会贴边走很长一段，最后再没有规律得走。套上结论交了一发WA了，之后分别预处理了GCD，改了最后跑的长度，在KSCD_的提醒下发现需要再交换 $a,b$ 重新跑一次。最后改到 50 才过了。在此期间KSCD_先想了B的差分，把B给了Iceturky，然后去想D。Iceturky过了G后用二分过了B。之后很长一段时间我在漫无目的的开题，看到M是提交答案，就开始想M。先想了一个看起来挺真的策略，然后打算多次跑去平均值，但是实际上策略假了，比正确答案多了一倍多。KSCD_在回宿舍前写完了D，把代码给了Iceturky调，在结束前几分钟终于调过了。一共过了 9 个，感觉是打的最爽得一次。

整场我主要写了水题和一个乱搞，后面的难题全靠Iceturky和KSCD_在切，希望还能有机会再和KSCD_、Iceturky打ICPC。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-07 21:50:31

Day-1

你说的对，但是在学文化课。

Day0

上午还是上文化课。中午终于可以脱离文化课的苦海了。坐大巴去济南，路上爽颓。到了之后发现是和上次同一个酒店，并且还是和同一个同学同屋，牛完了。颓了一会后本来打算重走去年流程去同一家吃饭，不过倒闭了……饭后依然是去了大润发买考试要吃的东西。试机还是得写分块啊。光速完成试机，回酒店稍微看了一下板子，然后和chb，KSCD，Iceturky一起颓。

Day1

酒店的早餐一点没有变。场上先写了T1T2的暴力，然后突然想到T1的特殊性质，写到一半突然会了正解。之后写了T3暴力。虽然很久没有写题了，但是手感还行。午餐时大家对于肯德基与麦当劳产生了分裂，Iceturky带领一部分同学去了麦当劳，chb带领一部分同学去了肯德基（include me）。下午好像也是一直在颓。晚饭前再次分裂，Iceturky与Cybrex两人独自City Walk，度过二人世界。其余人吃了必胜客。晚上还是在颓，从KCSD与Iceturky屋里离开前还唱了歌。

Day2

T1一眼有了思路，不到一个小时写完了，算了一眼时间复杂度选择相信省选评测姬的实力（虽然因此寄了）。T2T3只会暴力。遗憾离场。

出了考场雪下得很大了，教练买了烧饼和奶茶在路上吃，不过大巴花了3个小时走了20公里，中途ryp下车上厕所，回来车基本没有动。最后临时改变计划坐动车回潍坊。终于在七点半到了潍坊。可恶明天还要上学。

Day3-5

上文化课

Day 6

下午上信息课，翘掉去找KSCD和Iceturky，发现省选出了成绩，稳定发挥两天T1都挂了点分。不过本来也没打算进队。可能就此退役》

Day 7

chb来学校，下午放大周一起打球，拼尽全力无法战胜。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-11 22:07:55

有没有好心人给我买一件ATcoder的T恤衫~

Solution

纯模拟，做法很简单，能穿普通 T-shirt 就穿普通的，并且在每一次洗衣服之前以及最后一天之后，统计一下距离上一次洗衣服时需要多少件，取一个最大值就行了。

CODE

#include<bits\/stdc++.h>
using namespace std;
inline long long read() {
	long long s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s;
}
inline void write(long long x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x\/10);
	putchar(x%10+'0');
}
int n,m;
char s[100005];
int main(){
\/\/	freopen(".in","r",stdin);
\/\/	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>(s+1);
	int maxx=0;
	int sum=0;
	int summ=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='1'){
			if(summ<m){
				summ++;
			}
			else {
				sum++;
			}
		}
		else if(s[i]=='0'){
			maxx=max(maxx,sum);
			sum=0;
			summ=0;
		}
		else {
			sum++;
		}
	}
	maxx=max(maxx,sum);
	cout<<maxx;
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-14 21:53:31

代码比较好写，但是思考起来比较难

首先看出在两次翻转之间的左移和右移是可以互相抵消一部分的，之后就是比较难想到的一部分。

把翻转变成改变头和尾

规律

可以看到先翻转还是先移动结果一样，只是移动方向需要改变。具体为每遇到一个翻转就把原先累积的移动方向和头尾改变一下，最后再统一移动。

CODE

#include<bits\/stdc++.h>
#define int long long
using namespace std;
inline long long read() {
	long long s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s;
}
inline void write(long long x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x\/10);
	putchar(x%10+'0');
}
char s[1000005];
int n,flag,pos,len;
deque<char>q;
void make(){
	int u=abs(pos);
	if(u>len\/2){
		u=len-u;
		if(pos>0) pos=-u;
		else pos=u;
	}
	if(flag==0){
		if(pos>0){
			pos%=len;
			while(pos){
				q.push_back(q.front());
				q.pop_front();
				pos--;			
			}
		}
		else {
			pos=-pos;
			pos%=len;
			while(pos){
				q.push_front(q.back());
				q.pop_back();	
				pos--;			
			}
		}
	}
	else {
		if(pos>0){
			pos%=len;
			while(pos){
				q.push_front(q.back());
				q.pop_back();	
				pos--;			
			}
		}
		else {
			pos=-pos;
			pos%=len;
			while(pos){
				q.push_back(q.front());
				q.pop_front();	
				pos--;			
			}
		}
	}
}
void print(){
	if(flag==0){
		while(q.size()){
			putchar(q.back());
			q.pop_back();
		}
	}
	else {
		while(q.size()){
			putchar(q.front());
			q.pop_front();
		}
	}
}
signed main() {
	scanf("%s",s);
	len=strlen(s);
	for(int i=0;i<len;i++){
		q.push_front(s[i]);
	}
	n=read();
	for(int i=1;i<=n;i++){
		char ss[10];
		int x;
		scanf("%s",ss);
		if(ss[0]=='>'){
			x=read();
			pos+=x;
		}
		else if(ss[0]=='<'){
			x=read();
			pos-=x;
		}
		else {
			pos=-pos;
			flag=!flag;
		}
	}
	make();
	print();
	return 0;
}

个人码风不好，见谅。