SDUT月赛

首页 > 代码库 > SDUT月赛

2024-08-05 11:13:10 218人阅读

A题：点击打开链接

题意：一颗树上最初有n个苹果，晚上就会变成2*n，然后会有人来摘，摘完后剩下 (2*n)%m 然后如此循环，问会不会有一天出现苹果为0；

思路：如果不会出现肯定会出现周期，用哈希判剩余的苹果数是否出现过。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 1000060
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair<int,int>
#define ull unsigned long long
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n,m,vis[1000005];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(vis,0,sizeof(vis));
		int ok=1;
		vis[n]=1;n*=2;
		while(n%m)
		{
			n%=m;n*=2;
			if(!vis[n])
			{
				vis[n]=1;
			}
			else
			{
				ok=0;
				break;
			}
		}
		if(ok)puts("Yes");
		else puts("No");
	}
    return 0;
}

B题：点击打开链接

题意：给一个数列，求 ai-aj 最大，（i<j）

思路：预处理+枚举。首先逆向求出区间[i+1,n] 内的最小值dp[i]，然后正向枚举求max(a[i]-dp[i])

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 1000060
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair<int,int>
#define ull unsigned long long
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n,m,dp[1000005],a[1000005];
int main()
{
    while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",a+i);
		dp[n]=a[n];
		for(int i=n-1;i>=1;i--)
			dp[i]=min(a[i],dp[i+1]);
		int ans=-INF;
		for(int i=1;i<n;i++)
		ans=max(ans,a[i]-dp[i+1]);
		printf("%d\n",ans);

	}
    return 0;
}

C题：点击打开链接

题意：n个点，其中有一个起点和终点，现在要从起点遍历除起点和终点外的所有点然后再回到终点，求最小时间。

思路：先求出起点到所有点的最短路diss[] ,和终点到所有点的最短路 dise[] ,枚举所有点，因为是所有的路径同时进行，枚举 max(diss[i]+dise[i]) 最大的那条路都走完了的话，最短的肯定也走完了（比赛的时候没时间了。。A题卡了太久了没做完）

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 1000060
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair<int,int>
#define ull unsigned long long
using namespace std;
int n,m,diss[1005],dise[1005],st,sink;
bool vis[1005];
vector < pp > eg[100005];
void spfas(int src)
{
    queue <int> Q;
    memset(vis,0,sizeof(vis));
    memset(diss,INF,sizeof(diss));
    diss[src]=0;Q.push(src);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        vis[u]=0;
        for(int i=0;i<eg[u].size();i++)
        {
            int v=eg[u][i].first;
            int w=eg[u][i].second;
            if(diss[v]>diss[u]+w)
            {
                diss[v]=diss[u]+w;
                if(!vis[v])
                {
                    vis[v]=1;
                    Q.push(v);
                }
            }
        }
    }
}
void spfae(int src)
{
    queue <int> Q;
    memset(vis,0,sizeof(vis));
    memset(dise,INF,sizeof(dise));
    dise[src]=0;Q.push(src);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        vis[u]=0;
        for(int i=0;i<eg[u].size();i++)
        {
            int v=eg[u][i].first;
            int w=eg[u][i].second;
            if(dise[v]>dise[u]+w)
            {
                dise[v]=dise[u]+w;
                if(!vis[v])
                {
                    vis[v]=1;
                    Q.push(v);
                }
            }
        }
    }
}
int main()
{
	int T,u,v,c,cas=1;
	scanf("%d",&T);
    while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=0;i<=n;i++)
			eg[i].clear();
		while(m--)
		{
			scanf("%d%d%d",&u,&v,&c);
			eg[u].push_back(make_pair(v,c));
			eg[v].push_back(make_pair(u,c));
		}
		scanf("%d%d",&st,&sink);
		spfas(st);spfae(sink);
		int ans=-INF;
		for(int i=0;i<n;i++)
			ans=max(ans,diss[i]+dise[i]);
		printf("Case #%d: %d\n",cas++,ans);
	}
    return 0;
}

D题：点击打开链接

脑残题，找规律会出现循环节

题目大意是A说：why are you so diao B说：你猜 A说：你猜我猜不猜 B说：你猜我猜不猜你猜不猜 A说：。。

给出 A或B 和他们说的第几句话问这句话的字母缩写。

然后在脑中模拟一下这个脑残对话就ok了。。（ps不要一直往后想会疯掉的）

贴脑残代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 1000060
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair<int,int>
#define ull unsigned long long
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int main()
{
	char s[4];int n;
    while(scanf("%s %d",s,&n)!=EOF)
	{

		if(s[0]=='A')
		{
			if(n==1)
				puts("Waysd");
			else
			{
				string x="Ncwcbc";
				for(int i=3;i<=n;i++)
					x+="ncbcwcbc";
				cout<<x<<endl;
			}
		}
		else
		{
			if(n==1)
				puts("Nc");
			else
			{
				string y="Nc";
				for(int i=2;i<=n;i++)
					y+="wcbcncbc";
				cout<<y<<endl;
			}
		}
	}
    return 0;
}

E题：点击打开链接

题意：n杯水中有一杯是有毒的，毒性在一周内发作，现在要在一周内测出哪杯水有毒，问至少需要多少只小白鼠。

貌似这个问题网上比较火，二进制问题，给n杯水按二进制编号从1编到n ，然后取出二进制1代表有毒0代表无毒，分别取出二进制下末为是1的杯子编号的水混合，（依次是倒数第二位为1，倒数第三。。）假设二进制最多有x个位，然后派x只小白鼠来喝这些混合水，死了的是1，没死的是0，从左到右写下来然后转换成10进制就是对应有毒的杯子的编号。。

说白了这题就是求n转化成二进制有几位。

贴个java脑残代码。。

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		String a;
		while(in.hasNext()){
			a=in.next();
			BigInteger b=new BigInteger(a,10);
			System.out.println(b.toString(2).length());
		}
	}
}

F题：点击打开链接

裸拓扑排序，注意要字典序答案。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 1000060
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair<int,int>
#define ull unsigned long long
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int ans[30005],in[30005],tot,n,m;
vector <int> eg[100005];
void top_sort()
{
	priority_queue <int,vector<int>,greater<int> > s;tot=0;
	for(int i=1;i<=n;i++)
	{
		if(in[i]==0)
			s.push(i);
	}
	while(!s.empty())
	{
		int u=s.top();s.pop();
		ans[tot++]=u;
		for(int i=0;i<eg[u].size();i++)
		{
			int v=eg[u][i];
			in[v]--;
			if(in[v]==0)
				s.push(v);
		}
	}
	for(int i=0;i<tot;i++)
		if(i!=tot-1)
		printf("%d ",ans[i]);
	    else
		printf("%d\n",ans[i]);
}
int main()
{
	int u,v;
    while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(in,0,sizeof(in));
		for(int i=1;i<=n;i++)
			eg[i].clear();
		while(m--)
		{
			scanf("%d%d",&u,&v);
			eg[u].push_back(v);
			in[v]++;
		}
		top_sort();
	}
    return 0;
}

SDUT月赛

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > SDUT月赛

SDUT月赛

看完仍有疑问？有类似问题直接问程序猿