首页 > 代码库 > SDUT月赛
SDUT月赛
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个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。