2021 RoboCom 世界机器人开发者大赛-本科组（决赛）题解

7-1

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
 
using namespace std;
ll n,L;
ll x[N],y[N];
void solve()
{
    cin>>n>>L;
    for(int i=1;i<=n;i++)
    {
        if(i&1) 
        {
            cin>>y[i];
            x[i]=x[i-1];
        }
        else
        {
            cin>>x[i];
            y[i]=y[i-1];
        }
    }
    x[n+1]=0,y[n+1]=0;
    n++;
    ll now=0;
    cout<<0<<' '<<0<<'\n';
    for(int i=1;i<=n;i++)
    {
        ll len=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
        if(now+len>=L)
        {
            ll d=L-now;
            if(i&1)
            {
                if(y[i]>y[i-1])
                {
                    if(x[i]==0&&y[i-1]+d==0) continue;
                    cout<<x[i]<<' '<<y[i-1]+d<<'\n';
                    ll X=x[i],Y=y[i-1]+d;
                    while(Y+L<=y[i])
                    {
                        if(X==0&&Y+L==0) break;
                        cout<<X<<' '<<Y+L<<'\n';
                        Y+=L;
                    }
                    now=abs(x[i]-X)+abs(y[i]-Y);
                }
                else
                {
                    if(x[i]==0&&y[i-1]-d==0) continue;
                    cout<<x[i]<<' '<<y[i-1]-d<<'\n';
                    ll X=x[i],Y=y[i-1]-d;
                    while(Y-L>=y[i])
                    {
                        if(X==0&&Y-L==0) break;
                        cout<<X<<' '<<Y-L<<'\n';
                        Y-=L;
                    }
                    now=abs(x[i]-X)+abs(y[i]-Y);
                }
            }
            else
            {
                if(x[i]>x[i-1])
                {
                    if(x[i-1]+d==0&&y[i]==0) continue;
                    cout<<x[i-1]+d<<' '<<y[i]<<'\n';
                    ll X=x[i-1]+d,Y=y[i];
                    while(X+L<=x[i])
                    {
                        if(X+L==0&&Y==0) break;
                        cout<<X+L<<' '<<Y<<'\n';
                        X+=L;
                    }
                    now=abs(x[i]-X)+abs(y[i]-Y);
                }
                else
                {
                    if(x[i-1]-d==0&&y[i]==0) continue;
                    cout<<x[i-1]-d<<' '<<y[i]<<'\n';
                    ll X=x[i-1]-d,Y=y[i];
                    while(X-L>=x[i])
                    {
                        if(X-L==0&&Y==0) break;
                        cout<<X-L<<' '<<Y<<'\n';
                        X-=L;
                    }
                    now=abs(x[i]-X)+abs(y[i]-Y);
                }
            }
        }
        else now+=len;
    }
}
signed main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //ios;
    int _t=1;
    //cin>>_t;
    while(_t--) solve();
    system("pause");
    return 0;
}

7-2

#include <bits/stdc++.h>
#define int long long
const int N=1e5+10;
using namespace std;
typedef long long ll;
int n;
int a[N];
int cal(vector<int>v)
{
	int dp[N]={0};
	for(int i=0;i<n;i++)
		for(int j=0;j<i;j++)
		{
			if(v[i]>v[j]) dp[i]=max(dp[i],dp[j]+1);
		}
	int ret=0;
	for(int i=0;i<n;i++)
		ret=max(ret,dp[i]+1);
	return ret;
}
signed main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	int malen=1,ans=0;
	for(int i=0;i<(1<<n);i++)
	{
		deque<int>q;
		for(int j=0;j<n;j++)
		{
			if((i>>(n-j))&1) q.push_back(a[j]);
			else q.push_front(a[j]);
		}
		vector<int>v;
		for(auto x:q)
			v.push_back(x);
		
		int tlen=cal(v);
		if(tlen>malen)
		{
			malen=tlen;
			ans=i;
		}
		if(tlen==n) break;
	}
	cout<<malen<<'\n';
	for(int j=0;j<n;j++)
		if((ans>>(n-j))&1) cout<<'R';
		else cout<<'L';
	cout<<'\n';
	return 0;
}

7-3

#include <bits/stdc++.h>
#define int long long
const int N=1e5+10;
using namespace std;
typedef long long ll;
int n,tip,tlog;
unordered_map<string,unordered_map<string,int>>mp;
struct IPS{
	string ip;
	int num;
	bool operator < (const IPS &a) const
	{
		if(num!=a.num) return num>a.num;
		else return ip<a.ip;
	}
};
struct Record{
	string name;
	vector<IPS>ips;
	int cnt;
	bool operator < (const Record &a) const
	{
		if(ips.size()!=a.ips.size()) return ips.size()>a.ips.size();
		else
		{
			return name<a.name;	
		}	
	} 
};
vector<Record>records;
vector<Record>ret;
signed main()
{
	cin>>n>>tip>>tlog;
	for(int i=0;i<n;i++)
	{
		string name,ip;
		cin>>name>>ip;
		mp[name][ip]++;
	}
	
	for(auto [a,b]:mp)
	{
		int cnt=0;
		vector<IPS>ips;
		for(auto [aa,bb]:b)
		{
			cnt+=bb;
			ips.push_back({aa,bb});
		}
		sort(ips.begin(),ips.end());
		records.push_back({a,ips,cnt});		
	}
	for(auto r:records)
	{
		if(r.ips.size()>tip&&r.cnt>tlog) ret.push_back(r);
	}
	if(ret.size())
	{
		sort(ret.begin(),ret.end());
		for(auto r:ret)
		{
			cout<<r.name<<'\n';
			for(auto [ip,num]:r.ips)
			{
				cout<<ip<<' '<<num<<'\n';
			}
		}
	}
	else
	{
		sort(records.begin(),records.end());
		for(int i=0;records[i].ips.size()==records[0].ips.size();i++)
		{
			cout<<records[i].name<<'\n';
			for(auto [ip,num]:records[i].ips)
			{
				cout<<ip<<' '<<num<<'\n';
			}
		}
	}
	system("pause");
	return 0;
}