奇怪的问题
  • 板块灌水区
  • 楼主lanxi
  • 当前回复7
  • 已保存回复7
  • 发布时间2025/2/7 10:00
  • 上次更新2025/2/7 12:10:55
查看原帖
奇怪的问题
585657
lanxi楼主2025/2/7 10:00

rt,首先先贴上题面和我的代码(题面只需要看一下输入格式就行,代码写的对不对也不重要)

#include <cmath>
#include <queue>
#include <vector>
#include <complex>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define int long long
using namespace std;
const int amod = 998244353;
const int mod = 1e12+39;
queue <int> que[200001];
string t[200001];
queue <int> ept;
int ths[200001];
int hs[200001];
int a[200001];
int q[200001];

int pw(int x,int y)
{
	int c = 1;
	while(y)
	{
		if(y&1)
		{
			c = (c*x)%mod;
		}
		x = (x*x)%mod;
		y >>= 1;
	}
	return c;
}

int Hash(string s)
{
	int ans = 0;
	for(int i = 1;i <= s.length();i++)
	{
		ans *= 14;
		ans %= mod;
		ans += s[i-1];
		ans %= mod;
	}
	return ans;
}

#undef int
int main()
{
#define int long long

	int n,m;
	scanf("%lld %lld",&n,&m);
	for(int i = 1;i <= n;i++)
	{
		scanf("%lld",&a[i]);
		que[i].push(i);
	}
	for(int czcs = 1;czcs <= m;czcs++)
	{
		int op;
		scanf("%lld",&op);

		printf("%lld:%lld start\n",czcs,op);

		if(op == 1)
		{
			int x,y;
			scanf("%lld %lld",&x,&y);
			int idy = q[y];
			while(!que[idy].empty())
			{
				que[q[x]].push(que[idy].front());
				q[que[idy].front()] = q[x];
				que[idy].pop();
			}
			ept.push(idy);
		}
		else if(op == 2)
		{
			int x;
			scanf("%lld",&x);
			int idx = q[x];
			int idy;
			while(!ept.empty())
			{
				if(que[ept.front()].empty())
				{
					idy = ept.front();
					ept.pop();
					break;
				}
				ept.pop();
			}
			while(que[idx].front() != x)
			{
				que[idy].push(que[idx].front());
				q[que[idx].front()] = idy;
				que[idx].pop();
			}
			que[idy].push(x);
			q[x] = idy;
			que[idx].pop();
		}
		else
		{
			string s;
			int k;
			cin >> s;
			scanf("%lld",&k);

			printf("read\n");
			// cout << s << " " << k << endl;

			hs[1] = s[0]*pw(14,s.length()-1);
			for(int i = 2;i <= s.length();i++)
			{
				hs[i] = hs[i-1]+s[i-1]*pw(14,s.length()-i);
				hs[i] %= mod;
			}

			printf("hash s\n");
			// cout << s << " " << k << endl;

			queue <int> tq;
			for(int j = 1;j <= n;j++)
			{
				while(!tq.empty())
				{
					tq.pop();
				}
				while(!que[j].empty())
				{
					tq.push(que[j].front());
					t[j] += char(a[que[j].front()]+'0');
					que[j].pop();
				}
				while(!tq.empty())
				{
					que[j].push(tq.front());
					tq.pop();
				}
			}

			printf("change que->t\n");

			int ans = 1;
			for(int i = 1;i+k-1 <= s.length();i++)
			{
				int hsh = ((hs[s.length()]-hs[i-1]-(hs[s.length()]-hs[i+k-1]))%mod+mod)%mod*pw(14,i-1)%mod;
				int cnt = 0;
				for(int j = 1;j <= n;j++)
				{
					ths[1] = t[j][0]*pw(14,t[j].length()-1);
					for(int l = 2;l <= t[j].length();l++)
					{
						ths[l] = ths[l-1]+t[j][l-1]*pw(14,t[j].length()-l);
						ths[l] %= mod;
					}
					int tmp = hsh;
					if(t[j].length() > s.length())
					{
						tmp = (tmp*pw(14,t[j].length()-s.length())%mod);
					}
					for(int l = 1;l+k-1 <= t[j].length();l++)
					{
						int hst = ((ths[t[j].length()]-ths[l-1]-(ths[t[j].length()]-ths[l+k-1]))%mod+mod)%mod*pw(14,l-1)%mod;
						if(t[j].length() < s.length())
						{
							hst = (hst*pw(14,s.length()-t[j].length())%mod);
						}
						if(hst == tmp)
						{
							cnt++;
						}
					}
				}
				ans *= cnt;
				ans %= amod;
			}
			printf("%lld\n",ans);

			// cout << s << " " << k << endl;
			// cout << endl;
		}

		printf("%lld:%lld end\n",czcs,op);

		// cout << endl;
	}
	return 0;
}

当我输入

2 2
6 6
1 1 2
3 666666666666666666666666666666 1

时他的输出是正常的

1:1 start
1:1 end
2:3 start
read
hash s
change que->t
0
2:3 end

但是当我增加一条操作变成

2 3
6 6
1 1 2
3 666666666666666666666666666666 1
2 1

时,他的输出却变成了

1:1 start
1:1 end
2:3 start

最神奇的是,当我把代码的第185行的注释解掉,他就又有输出了?

这是什么原因,求解答QAQ

2025/2/7 10:00
加载中...