校赛总结——————自闭的一天

比眉伴天荒 2022-02-25 08:42 176阅读 0赞

这次校赛打的成绩跟屎一样，难受了好久，自闭了好久。

### 文章目录 ###

*  A \[Asia区域赛\](https://hpuoj.com/contest/16/problem/A/) (1.0 sec / 512 MB)
 *  B \[Asia区域制\](https://hpuoj.com/contest/16/problem/B/) (1.0 sec / 512 MB)
 *  C \[Asia区域宫\](https://hpuoj.com/contest/16/problem/C/) (1.0 sec / 512 MB)
 *  D \[Asia区域阵\](https://hpuoj.com/contest/16/problem/D/) (1.0 sec / 512 MB)(未补)
 *  E \[Mo的游戏\](https://hpuoj.com/contest/16/problem/E/) (1.0 sec / 512 MB)
 *  F \[Mo的极限\](https://hpuoj.com/contest/16/problem/F/) (1.0 sec / 512 MB)(待补)
 *  G \[Mo的数学\](https://hpuoj.com/contest/16/problem/G/) (1.0 sec / 512 MB)(已补)
 *  H \[Mo的面积\](https://hpuoj.com/contest/16/problem/H/) (1.0 sec / 512 MB)
 *  I \[安全距离\](https://hpuoj.com/contest/16/problem/I/) (2.0 sec / 512 MB)(待补)
 *  J \[简单递归\](https://hpuoj.com/contest/16/problem/J/) (1.0 sec / 512 MB)
 *  K \[高度期望\](https://hpuoj.com/contest/16/problem/K/) (1.0 sec / 512 MB)
 *  L \[最优规划\](https://hpuoj.com/contest/16/problem/L/) (1.0 sec / 512 MB)(已补)

# A [Asia区域赛][Asia] (1.0 sec / 512 MB) #

水题，几个数加起来输出

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e5+7;
    int a[MAXN];
    
    int main()
    {
        
    	cout<<29+58+87+11+1+1<<endl; 
    	return 0;
    }

# B [Asia区域制][Asia 1] (1.0 sec / 512 MB) #

也是简单题，Wa了好几次，

Wa题原因：

刚开始也想到了让字符的每四位输出一个十六进制字符，但是还要考虑字符串处理，不满四位的话得前面补零

周六(昨天)，天梯赛做字符串处理的题做得要吐，不想再处理字符串了，于是想用另外一种方法做（将二进制数转化成十进制，在转化成十六进制输出）

因为忘记考虑字符串的长度(1e6)转化成数字是要溢出的，这个错误导致我浪费了一个小时在做这道题，对我自信心打击很大，心情也是极为崩溃的，上百人都做出来了这道题，而我还在Wa.

然后去找其它题去做，看到 [ J 简单递归][J] 过的人比较多,然后就去做这一个了，

最后还是用字符串处理的

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    string change(string s)
    {
        
    	string res="";
    	if(s=="0000")	res = "0";
    	if(s=="0001")	res = "1";
    	if(s=="0010")	res = "2";
    	if(s=="0011")	res = "3";
    	if(s=="0100")	res = "4";
    	if(s=="0101")	res = "5";
    	if(s=="0110")	res = "6";
    	if(s=="0111")	res = "7";
    	if(s=="1000")	res = "8";
    	if(s=="1001")	res = "9";
    	if(s=="1010")	res = "a";
    	if(s=="1011")	res = "b";
    	if(s=="1100")	res = "c";
    	if(s=="1101")	res = "d";
    	if(s=="1110")	res = "e";
    	if(s=="1111")	res = "f";
    	return res;
    }
    
    int main()
    {
        
    	int t;
    	cin>>t;
    	while(t--)
    	{
        
    		string s;
    		cin>>s;
    		if(s.length()%4==0)
    		{
        
    			for(int i=0;i<s.length();i+=4)
    			{
        
    				string hex = s.substr(i,4);
    				cout<<change(hex);
    			}
    			cout<<endl;	
    		}
    		else
    		{
        
    			reverse(s.begin(),s.end());
    			while(s.length()%4!=0)	s+="0";
    			reverse(s.begin(),s.end());
    //			cout<<s<<endl;
    			for(int i=0;i<s.length();i+=4)
    			{
        
    				string hex = s.substr(i,4);
    				cout<<change(hex);
    			}
    			cout<<endl;
    		}
    	}
    	return 0;
    }

# C [Asia区域宫][Asia 2] (1.0 sec / 512 MB) #

最后的一个多小时我才在想这道题。

负对角线上如果被占满了，那就不能解救

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 2e4+7;
    int a[MAXN];
    
    int main()
    {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            int t,m,n,x,y;
            cin>>t;
            while(t--)
            {
        
                    memset(a,0,sizeof(a));
                    cin>>n>>m;
                    for(int i=0;i<m;++i)
                    {
        
                            cin>>x>>y;
                            a[x+y]++;
                    }
                    int cnt = 2;
                    int flag = 0;
                    for(int i=3;i<=n+1;++i,++cnt)
                            if(a[i]==cnt)
                            {
        
                                    flag = 1;
                                    break;
                            }
                    if(!flag)
                    {
        
                            cnt = n;
                            for(int i=n+1;i<2*n;++i,--cnt)
                                    if(a[i]==cnt)
                                    {
        
                                            flag = 1;
                                            break;
                                    }
                    }
                    if(!flag)        cout<<"Yes "<<2*(n-1)<<endl;
                    else            cout<<"No"<<endl;
            }
            return 0;
    }

# D [Asia区域阵][Asia 3] (1.0 sec / 512 MB)(未补) #

还不会。。

# E [Mo的游戏][Mo] (1.0 sec / 512 MB) #

改bug改了好久，不知道为啥，脑残了好久

思路：将字符及其位置存到结构体里，然后按照字符升序排列，字符相同的话按照位置升序排列，

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e6+7;
    int c[500];
    int dis[MAXN];
    struct node{
        
    	char ch;
    	int id;
    
    }a[MAXN];
    
    bool cmp(node a,node b)
    {
        
    	return a.ch==b.ch?a.id<b.id:a.ch<b.ch;
    }
    
    int main()
    {
        
    	char s[MAXN];
    	scanf("%s",s);
    	int len = strlen(s);
    	memset(c,0,sizeof(c));
    	memset(dis,0x3f,sizeof(dis));
    	for(int i=0;i<len;++i)
    	{
        
    		c[s[i]]++;
    		a[i].id = i;
    		a[i].ch = s[i];		
    	}
    	sort(a,a+len,cmp);	
    	for(int i=0;i<len;++i)
    	{
        
    		if(c[a[i].ch]<=1)	
    		{
        
    			dis[a[i].ch] = 0;
    			continue;
    		}
    		int k = 0;
    		while(a[i+1].ch==a[i].ch)
    		{
        
    			if(abs(a[i+1].id - a[i].id)<dis[a[i].ch])
    				dis[a[i].ch] = abs(a[i].id - a[i+1].id);
    			++i;
    		}
    			dis[a[i].ch] = len - dis[a[i].ch];
    	}
    	
    	for(int i='a';i<='z';++i)
    		if(c[i])
    			printf("%c:%d\n",i,dis[i]);
    	for(int i='A';i<='Z';++i)
    		if(c[i])
    			printf("%c:%d\n",i,dis[i]);
    	return 0;
    }
    /*
    abcdedff
    */

# F [Mo的极限][Mo 1] (1.0 sec / 512 MB)(待补) #

这个没来得及看，回头补一下。

# G [Mo的数学][Mo 2] (1.0 sec / 512 MB)(已补) #

比赛的时候没做出来，

当时也想到了质因子分解，不过我想的方法比较笨，就是给前1e6的数字打出质因子表，然后打出来m的质因子，再一个一个比较，如果有相同的质因子就不相乘，TLE了。

然而这才是正解：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll MAXN = 1e6+7;
    const ll  MOD = 1e9+7;
    bool vis[MAXN];
    ll n,m;
    
    
    vector<ll> Get(ll n)
    {
        
            vector<ll> d;
            for(ll i=2;i*i<=n;++i)
            {
        
                    if(n%i==0)
                    {
        
                            d.push_back(i);
                            while(n%i==0)   n/=i;
                    }
            }
            if(n!=1)        d.push_back(n);
            return d;
    }
    
    int main()
    {
        
            while(cin>>n>>m)
            {
        
                    vector<ll> d;
                    d = Get(m);
                    memset(vis,0,sizeof(vis));
                    for(ll i=0;i<d.size();++i)
                    {
        
                            for(ll j=1;j*d[i]<=n;++j)
                                    vis[d[i]*j] = 1;
                    }
                    ll ans = 1;
                    for(ll i=1;i<=n;++i)
                            if(!vis[i])
                                    ans = (ans*i)%MOD;
                    cout<<ans<<endl;
            }
            return 0;
    }

不过听说标程是容斥定理。。回头学习一下

# H [Mo的面积][Mo 3] (1.0 sec / 512 MB) #

这是我的代码，大佬们写的代码回头我也得学习一下，

刚开始的思路是枚举所有情况，可是写了好久都挂了。

最后看了一下范围，直接开了MAXN\*MAXN的数组，暴力过了

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e3+7;
    bool vis[MAXN][MAXN];
    
    
    int main()
    {
        
    	int a1,b1,c1,d1;
    	int a2,b2,c2,d2;
    	cin>>a1>>b1>>c1>>d1;
    	cin>>a2>>b2>>c2>>d2;
    	memset(vis,0,sizeof(vis));
    	for(int i=a1;i<c1;++i)
    		for(int j=b1;j<d1;++j)
    			vis[i][j] = 1;
    	for(int i=a2;i<c2;++i)
    		for(int j=b2;j<d2;++j)
    			vis[i][j] = 1;
    	int ans = 0;
    	for(int i=0;i<MAXN;++i)
    		for(int j=0;j<MAXN;++j)
    			if(vis[i][j])	ans++;
    	cout<<ans<<endl;
    	return 0;
    }

# I [安全距离][Link 1] (2.0 sec / 512 MB)(待补) #

还不会。。

# J [简单递归][J] (1.0 sec / 512 MB) #

将递归改写成递推就好了

f ( n ) = \{ 1 n=1||n=2 f ( n − 1 ) < < 1 + f ( n − 2 ) > > 1 e l s e f(n) =\\begin\{cases\}1 &\\text\{n=1||n=2 \} \\\\ f(n-1)<<1+f(n-2)>>1 & else\\end\{cases\} f(n)=\{ 1f(n−1)<<1\+f(n−2)>>1n=1||n=2 else

记得要取模呀

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MOD  = 1e9+7;
    const int MAXN = 1e6+7;
    ll a[MAXN];
    int main()
    {
        
    	a[1] = a[2] = 1;
    	for(ll i=3;i<MAXN;++i)
    		a[i] = ((a[i-1]<<1)%MOD + (a[i-2]>>1)%MOD)%MOD;
    	int t,n;
    	cin>>t;
    	while(t--)
    	{
        
    		cin>>n;
    		cout<<a[n]<<endl;
    	}
    	return 0;
    }

# K [高度期望][Link 2] (1.0 sec / 512 MB) #

简单贪心，从短的树开始拔高

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e5+7;
    int a[MAXN];
    int n,m;
    
    
    int main()
    {
        
    	while(cin>>n>>m)
    	{
        
    		int num = n*m;
    		int sum = 0;
    		for(int i=0;i<n;++i)
    		{
        
    			cin>>a[i];
    			sum += a[i];
    		}
    		if(sum>=num)
    		{
        
    			cout<<0<<endl;
    			continue;
    		}
    		else
    		{
        
    			
    			int cnt = 0;
    			sort(a,a+n);
    			for(int i=0;i<n;++i)
    			{
        
    				sum += 1000-a[i];
    				cnt++;
    				if(sum>=num)
    				break;
    			}
    			cout<<cnt<<endl;
    		}
    		
    	}
    	return 0;
    }

# L [最优规划][Link 3] (1.0 sec / 512 MB)(已补) #

对并查集的理解有待加强。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 2e5+7;
    ll n,m,s;
    ll pre[MAXN];
    struct Road{
        
            ll x,y,cost;
    }w;
    void init(ll n)
    {
        
            for(ll i=0;i<=n;++i)
                    pre[i] = i;
    }
    ll find(ll x)
    {
        
            return pre[x] == x ? x : pre[x] = find(pre[x]);
    }
    void join(ll x,ll y)
    {
        
            x = find(x);
            y = find(y);
            if(x!=y)
                    pre[x] = y;
    }
    bool cmp(Road a,Road b)
    {
        
            return a.cost<b.cost;
    }
    
    int main()
    {
        
    
            scanf("%lld %lld %lld",&n,&m,&s);
            init(n);
            for(ll i=0;i<m;++i)
            {
        
                    scanf("%lld %lld %lld",&w.x,&w.y,&w.cost);
                    join(w.x,w.y);
            }
            vector<Road> d;
            for(ll i=0;i<s;++i)
            {
        
                    scanf("%lld %lld %lld",&w.x,&w.y,&w.cost);
                    d.push_back(w);
            }
            sort(d.begin(),d.end(),cmp);
            ll sum = 0;
            ll cnt = 0;
            for(int i=0;i<d.size();++i)
            {
        
                    if(find(d[i].x)!=find(d[i].y))
                    {
        
                            join(d[i].x,d[i].y);
                            sum += d[i].cost;
                    }
            }
            for(int i=1;i<=n;++i)
            {
        
                    if(find(i)!=find(1))
                            cnt++;
            }
            // cout<<cnt<<endl;
            if(cnt)      cout<<"Concubines can't do it."<<endl;
            else            cout<<sum<<endl;
    
            return 0;
    }

--------------------

题目并不是很难，坑多一些而已，可是自己为什么做的这么烂？这个真的得好好的反思一下了。

[Asia]: https://hpuoj.com/contest/16/problem/A/
[Asia 1]: https://hpuoj.com/contest/16/problem/B/
[J]: https://hpuoj.com/contest/16/problem/J/
[Asia 2]: https://hpuoj.com/contest/16/problem/C/
[Asia 3]: https://hpuoj.com/contest/16/problem/D/
[Mo]: https://hpuoj.com/contest/16/problem/E/
[Mo 1]: https://hpuoj.com/contest/16/problem/F/
[Mo 2]: https://hpuoj.com/contest/16/problem/G/
[Mo 3]: https://hpuoj.com/contest/16/problem/H/
[Link 1]: https://hpuoj.com/contest/16/problem/I/
[Link 2]: https://hpuoj.com/contest/16/problem/K/
[Link 3]: https://hpuoj.com/contest/16/problem/L/