SGU 100 A+B ：太神不会
SGU 101 Domino:
题目大意：有Ｎ张骨牌，两张骨牌有两面有０到６的数字，能相连当且仅当前后数字相同，问能否有将Ｎ张骨牌连接的方案？思路：裸的欧拉回路，注意自环，连通
//sgu101
#include<iostream>
#include<cstdio>
#include <math.h>
#include<algorithm>
#include<string.h>
#include<queue>
#define MOD 1000003
#define maxn 2009
using namespace std;
int head[maxn],ans[maxn],top,now=,next[maxn],point[maxn];
int degree[maxn],sum=;
bool visit[maxn],ss[maxn],sign[maxn];
void add(int x,int y,bool si){
next[++now]=head[x];head[x]=now;
point[now]=y;ss[now]=si;
}
void dfs(int s){
for(int i=head[s];i;i=next[i])if(!visit[i>>]){
sum++;
int u=point[i];visit[i>>]=;dfs(u);
ans[++top]=i>>;sign[top]=ss[i];
}
}
int main()
{
int n,x,y,cnt=,s=;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);add(x,y,);add(y,x,);
degree[x]++;degree[y]++;s=x;
}
for(int i=;i<=;i++)if(degree[i]&)cnt++,s=i;dfs(s);
if(sum!=n ||cnt>){printf("No solution\n");return ;}
for(int i=top;i>=;i--){
printf("%d ",ans[i]);
if(sign[i]==)printf("+\n");else printf("-\n");
}
return ;
}
SGU 102 Coprimes：
题目大意：求小于ｎ与ｎ互质的数的个数 思路：欧拉函数哪家强
//sgu101
#include<iostream>
#include<cstdio>
#include <math.h>
#include<algorithm>
#include<string.h>
#include<queue>
#define MOD 1000003
#define maxn 2009
using namespace std;
int phi(int n)
{
int ret=n;
for(int i=;i*i<=n;i++)
{
if(n%i==)ret=(ret/i)*(i-);
while(n%i==)n/=i;
}
if(n>)ret=ret/n*(n-);
return ret;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",phi(n));
return ;
}
SGU 103 Traffic Lights
题目大意: 给一个无向图,每个节点有一个红绿灯(难道俄罗斯的灯是蓝紫灯?)灯会变换,能通过一条路当且仅当在通过前两个灯的颜色一样,问从s到t的最短时间是多少 思路:裸的SPFA，问题就是当不能通过时你得输出０！！！不然就会死在第６个点
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 50000
using namespace std;
int tic[maxn],tib[maxn],ci[maxn],ric[maxn],s,t,n,m,now=;
int head[maxn],next[maxn],point[maxn],value[maxn],dist[maxn],pre[maxn],ans[maxn];
char ch[];
int col(int now,int l)
{
if(now<ric[l])return ci[l];
now-=ric[l];
int u,flag=;
if(ci[l])u=tic[l];else u=tib[l];
if(now%(tib[l]+tic[l])>=u)return ci[l];else return ci[l]^;
}
int remai(int now,int l)
{
if(now<ric[l])return ric[l]-now;
now=(now-ric[l])%(tic[l]+tib[l]);
int u;
if(ci[l])u=tic[l];else u=tib[l];
if(u-now>)return u-now;else return tic[l]+tib[l]-now;
}
int tim(int now,int l,int r,int k)
{
if(k==)return -;
int u=col(now,l),v=col(now,r);
if(u==v)return ;
u=remai(now,l);v=remai(now,r);
if(u==v)
{
int uu=tim(now+u,l,r,k+);
if(uu==-)return -;else return u+uu;
}
else return min(u,v);
}
void add(int x,int y,int v)
{
next[++now]=head[x];
head[x]=now;
point[now]=y;
value[now]=v;
}
int spfa(int s,int t)
{
memset(dist,-,sizeof(dist));
dist[s]=;
int visit[maxn]={};
visit[s]=;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();
visit[u]=;
q.pop();
for(int i=head[u];i;i=next[i])
{
int k=point[i];
int cost=tim(dist[u],k,u,);
if(cost==-)continue;else cost+=value[i];
if(dist[u]+cost<dist[k] || dist[k] == -)
{
pre[k]=u;
dist[k] = dist[u] + cost;
if(!visit[k])
{
visit[k] = ;
q.push(k);
}
}
}
}
if(dist[t]==-)return ;else return dist[t];
}
int main()
{
int s,t,x,y,v,h=;
scanf("%d%d%d%d",&s,&t,&n,&m);
for(int i=;i<=n;i++)
{
scanf("%s%d%d%d",ch+,&ric[i],&tib[i],&tic[i]);
if(ch[]=='B')ci[i]=;else ci[i]=;
}
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&v);
add(x,y,v);
add(y,x,v);
}
printf("%d\n",spfa(s,t));
int u=t;
while(pre[u]!=)
{
ans[++h] = u;
u = pre[u];
}
ans[++h]=s;
for(int i=h;i>=;i--)
{
printf("%d ",ans[i]);
}
printf("%d\n",ans[]);
return ;
}
SGU 104 Little shop of flowers
题目大意:有V个花瓶,F束花,Ｆ束花只能按一定顺序插入花瓶，并且插入某个花瓶的美感度是固定的,问美感读最大是多少 思路:裸dp，转移方程在代码里，加个转移就好了
#include<iostream>
#include<cstdio>
using namespace std;
//dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a[i][j]);
int dp[][],a[][],ans[];
bool pre[][];
int main()
{
int f,v;
scanf("%d%d",&f,&v);
for(int i=;i<=f;i++)
{
for(int j=;j<=v;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=;i<=f;i++)
{
dp[i][]=-0x3f3f3f3f;
for(int j=;j<=v;j++)
{
if(dp[i][j-]>dp[i-][j-]+a[i][j])
{
dp[i][j]=dp[i][j-];
pre[i][j]=;
}
else
{
dp[i][j]=dp[i-][j-]+a[i][j];
pre[i][j]=;
}
}
}
printf("%d\n",dp[f][v]);
int u=f,h=;
for(int i=v;i>=;i--)
{
if(!pre[u][i])
{
u--;
ans[++h]=i;
}
if(u==)break;
}
for(int i=h;i>=h-f+;i--)
{
printf("%d ",ans[i]);
}
return ;
}
SGU 105 Div 3
题目大意:给你 1 12 123...12345678910...的数列,问你前ｎ个数中有多少能被３整除？思路:能被三整除的数当且仅当所有十进位数的和能被３整除，于是就能用等差数列求和乱搞了
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
long long n;
while (scanf("%I64d",&n)!=EOF)
{
long long u=n/;
u<<=;
if((n+)%==)u++;
printf("%I64d\n",u);
}
return ;
}
SGU 107 987654321 problem
题目大意:有多少Ｎ位十进制数的平方的尾数是987654321思路:暴力打表后发现９位数一共有８个数满足，因此无论多少位只要尾数是这８个数都OK，由于不能有前导0，因此９位数的情况单独考虑，本来以为要高精度来着,马上意识到答案是720000....的形式 sgu第一次这么善良
/*
111111111 12345678987654321
119357639 14246245987654321
380642361 144888606987654321
388888889 151234567987654321
611111111 373456789987654321
619357639 383603884987654321
880642361 775530967987654321
888888889 790123456987654321
*/
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
if(n<=)printf("");
else if(n==)printf("");
else
{
printf("");
for(int i=;i<=n-;i++)printf("");
}
puts("");
return ;
}
SGU108 Self-numbers 2
题目大意:一个数n的后继是这个数本身加上它十进制位所有的数字,但有些数不能成为任何数的后继，找出第Ｎ个这样的数字 思路:直接按照题目模拟会ＭＬＥ啊啊啊啊,看了题解才想到一个数的后继最多只是这个数＋64，然后给优化下
#include<cstdio>
int ans[],x,h;
bool flag[];
int f(int x)
{
int ans=x;
while(x!=)
{
ans+=x%;
x/=;
}
return ans;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
if(flag[i%]==)
{
ans[++h]=i;
}
flag[f(i)%]=;
flag[i%]=;
}
printf("%d\n",h);
for(int i=;i<=k;i++)
{
scanf("%d",&x);
printf("%d ",ans[x]);
}
}
SGU 123 The sum 因为ｋ很小，所以就考你会不会c语言
#include<iostream>
#include<cstdio>
#define maxn 1000
using namespace std;
long long fib[maxn],sum[maxn];
int main()
{
int k;
fib[]=fib[]=;
sum[]=;sum[]=;
for(int i=;i<=;i++)
{
fib[i]=fib[i-]+fib[i-];
sum[i]=sum[i-]+fib[i];
}
cin>>k;
cout<<sum[k];
return ;
}
SGU 134 就是求一个树的重心
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define maxn 52010
#define LLD "%I64d"
using namespace std;
long long head[maxn],n,next[maxn],ans=1ll<<;
long long ver[maxn],point[maxn],ans_num,siz[maxn],now;
bool visit[maxn];
void add(int x,int y)
{
next[++now]=head[x];
head[x]=now;
point[now]=y;
}
void dfs(int k)
{
visit[k]=;
siz[k]=;
long long v=;
for(int i=head[k];i;i=next[i])
{
int u=point[i];
if(visit[u]==)continue;
dfs(u);
siz[k]+=siz[u];
v=max(v,siz[u]);
}
v=max(v,n-siz[k]);
if(v<ans)
{
ans_num=;
ver[ans_num]=k;
ans=v;
}
else if(v==ans)ver[++ans_num]=k;
}
int main()
{
ans=1ll<<;
now=;
memset(visit,,sizeof(visit));
memset(head,,sizeof(head));
int x,y;
scanf(LLD,&n);
if(n==)while();
for(int i=;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs();
sort(ver+,ver++ans_num);
printf(LLD " "LLD"\n",ans,ans_num);
for(int i=;i<ans_num;i++)
{
printf(LLD " ",ver[i]);
}
printf(LLD "\n",ver[ans_num]);
return ;
}