2019山東ACM省賽補題題解

Wandering Robot
題意：
大體意思就是一個機器人按照指定的路線走來走去，最后求最遠點和初始點（0,0）的距離
思路：
1.確定最遠點
第一次回圈路徑確定之后，其他的回圈基本都是在平移，最遠點可能是在最后一次回圈但是也很有可能在第一次回圈
2.確定最遠點的位置
K的值特別的大，所以肯定不能用for回圈來確定最后的位置
通過第一次回圈和以后路徑的平移來確定最后的位置
第一次的末位置是第二次回圈的初位置，通過第一次的平移規律*（k-1）推出最后一次回圈的初位置，根據位置移動方案推出最后一次回圈所有的位置并比較他們跟初始點的距離，計算距離最遠的點
3.比較第一次和最后一次
最后一次回圈的點的距離值與最后一次回圈的點的距離值相比較，求max最大值

#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define ll long long
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {

        ll n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        ll x=0,y=0;
        ll xn=0;
        for(ll i=0; i<n; i++)
        {
            if(s[i]=='U')
                y++;
            if(s[i]=='D')
                y--;
            if(s[i]=='L')
                x--;
            if(s[i]=='R')
                x++;

            if(xn<fabs(x)+fabs(y))
            {
                xn=fabs(x)+fabs(y);
            }
        }

        ll sumx=(k-1)*x;
        ll sumy=(k-1)*y;
        ll maxx=0;
        for(ll i=0; i<n; i++)
        {
            if(s[i]=='U')
                sumy++;
            if(s[i]=='D')
                sumy--;
            if(s[i]=='L')
                sumx--;
            if(s[i]=='R')
                sumx++;
            if(maxx<fabs(sumx)+fabs(sumy))
            {
                maxx=fabs(sumx)+fabs(sumy);
            }
        }
        cout<<max(xn,maxx)<<endl;
    }
}

Stones in the Bucket
題意：
n桶石頭，選擇從桶中洗掉一個石頭或者把其中一個石頭從一個桶移動到另一個桶，這兩種操作各是一次操作，求最少操作幾次，使每堆石頭的數量一樣，
思路：
求數量多于平均值的桶多出的那部分值的總和，因為這部分值早晚都是要被丟掉或者是移到別的桶，

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int num[100005];
int main()
{
    ll t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        ll num1=0,ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>num[i];
            num1=num1+num[i];
        }
        ll m=num1/n;
        for(int i=1;i<=n;i++)
        {
            if(num[i]>m)
            {
                ans=ans+(num[i]-m);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Happy Equation
（這道題當時沒做出來，后來比賽結束，看的網上的大佬的思路和代碼，學習的，最后自己整理的）
題意：
求滿足ax≡xa(mod 2p)在1-2^p范圍內的X的個數
思路：
1.當a為奇數的時候，為1，
2.當a為偶數的時候a=2x
指數<n時，用暴力
指數>n時，求出在m中?x的倍數

#include<bits/stdc++.h>
#define ll long long
using namespace std;

long long pg(ll a,ll b,ll mod)
{
	ll temp=a,ans=1;
	while(b!=0)
	{
		if(b&1)
        ans=(ans*temp)%mod;
		temp=(temp*temp)%mod;
		b>>=1;
	}
	return ans;
}
//打表函式
void init()
{
	ll ans=0;
	ll mod=1<<20;
	for(int a=1;a<=50;a++)
	{
		for(int i=1;i<=20;i++)
		{
			if(pg(a,i,mod)%mod==pg(i,a,mod)%mod)
			{
				ans++;
			}
		}
		if(a&1)	cout<<"奇數"<<endl;
		cout<<ans<<endl;

		ans=0;
	}

}
int main()
{
//	init();
	ll t;
	cin>>t;
	while(t--)
	{
		ll a,p;
		cin>>a>>p;
		if(a&1)
		{
			cout<<"1"<<endl;
			continue;
		}
		else
		{
			ll ans=0;
			ll mod=1<<p;
			for(int i=1;i<=p;i++)
			{
				if(pg(a,i,mod)%mod==pg(i,a,mod)%mod)
				{
					ans++;
				}
			}
			ll q1;
				q1=p/a;
			if(p%a)
				q1++;
			ll l=1<<q1;
			ans+=(mod/l-p/l);
			cout<<ans<<endl;
		}

	}
	return 0;
}

Game on a Graph
題意：
給出一個連通圖的節點數，邊數
有兩個隊伍，給出一個順序代表順序輪到哪個隊伍，就要在這個圖中刪去一條邊，如果刪去某一條邊圖不連通了，這個隊伍就失敗，最后輸出勝利的隊伍
思路：
關鍵在于搞清楚不連通時的臨界狀態，不連通的前一個狀態就是形成了一個單只的圖（每兩個頂點只有一條邊相連）n個點的圖若要聯通，最少要n-1條邊，

#include<bits/stdc++.h>
using namespace std;
//speed_up
int main()
{
    long long t,n;
    string s;
    cin>>t;
    while(t--)
    {
        long long a1,a2,a3;
        cin>>n>>s>>a1>>a2;
        for(int i=0;i<a2;++i)
        {
            cin>>a3>>a3;
        }
        long long ans=(a2-a1+1)%n;
        if(s[ans]=='2')
        {
            cout<<1<<endl;
        }
        else
        {
            cout<<2<<endl;
        }
    }
}