noip 2014

  • P1328 生活大爆炸版石头剪刀布
  • P1351 联合权值
  • P1941 飞扬的小鸟
  • P2038 无线网络发射器选址
  • P2296 寻找道路
  • P2312 解方程

    P1328 生活大爆炸版石头剪刀布

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    var c:array[0..4,0..4] of 0..1
    =((0,0,1,1,0),
    (1,0,0,1,0),
    (0,1,0,0,1),
    (0,0,1,0,1),
    (1,1,0,0,0));
    n,aa,bb,i,sa,sb,ahh,bhh:longint;
    a,b:array[0..200] of longint;
    begin
    read(n,aa,bb);
    for i:=1 to aa do
    read(a[i]);
    for i:=1 to bb do
    read(b[i]);
    sa:=0;
    sb:=0;
    for i:=1 to n do
    begin
    if i mod aa=0 then ahh:=aa else ahh:=i mod aa;
    if i mod bb=0 then bhh:=bb else bhh:=i mod bb;
    inc(sa,c[a[ahh],b[bhh]]);
    inc(sb,c[b[bhh],a[ahh]]);
    end;
    write(sa,' ',sb)
    end.

P1351 联合权值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<set>  
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
vector<int> d[200010];
int n,i,j,x,y;
long long M,sum;
int a[200010];
int main()
{
scanf("%d",&n);
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
d[x].push_back(y);
d[y].push_back(x);
}
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
for (i=1;i<=n;i++)
{
long long max1=0;
long long max2=0;
//int s1=0,s2=0;//s1:存和,s2:存平方和
long long s1=0,s2=0;
int s=d[i].size();
for (j=0;j<s;j++)
{
if (a[d[i][j]]>=max1)
{
max2=max1;
max1=a[d[i][j]];
} else
if (a[d[i][j]]>max2) max2=a[d[i][j]];
//s1+=a[d[i][j]];
//s2+=(a[d[i][j]]*a[d[i][j]]);
s2=s1;
s1+=a[d[i][j]];
sum+=(s2*a[d[i][j]]);
sum%=10007;
}
//sum=sum+((s1*s1-s2));
//sum%=10007;
M=max(M,max1*max2);
}
sum*=2;
cout<<M<<" "<<sum%10007;
return 0;
}

P1941 飞扬的小鸟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9') {k=k*10+(s-'0');s=getchar();}
return k*base;
}
const int maxn=10010,maxm=1010;
int X,n,m,k;//n*m的界面,k:水管数量
int hi[maxn],low[maxn];
int Map[maxn];//标记是否有管道
int Ms[maxn],Mx[maxn];//Ms上边沿,Mx下边沿
int dp[maxn][maxm];
int INF,Min,Last,flag,ans;
int main()
{
n=read();m=read();k=read();
for (int i=1;i<=n;i++) hi[i]=read(),low[i]=read();
for (int i=1;i<=k;i++)
{
X=read(),Map[X]=1;
Last=max(X,Last);
Mx[X]=read(),Ms[X]=read();
}
memset(dp,0x3f3f3f3f,sizeof(dp));//初始化
INF=dp[1][1];
memset(dp[0],0,sizeof(dp[0]));//第0列
for (int i=1;i<=n;i++)
{
for (int j=0;j<=m;j++)
{
if (j>=hi[i])//判断是否越界
{
if (((Map[i-1])&&(j-hi[i]>Mx[i-1])&&(j-hi[i]<Ms[i-1]))||(!Map[i-1]))//可以从j-hi[i]这个位置跳过来
dp[i][j]=min(dp[i][j],dp[i-1][j-hi[i]]+1);//点一次
dp[i][j]=min(dp[i][j],dp[i][j-hi[i]]+1);//连点几次,如果dp[i][j-h[i]]无法到达,那么无法更新
}
if (j>=m-hi[i])//i-1列的m-hi[i]~m行都能跳到第i列的m行,所以需要特判
{
if ((Map[i-1]&&(j>Mx[i-1]&&j<Ms[i-1]))||(!Map[i-1]))//可以转移过来
dp[i][m]=min(dp[i][m],dp[i-1][j]+1);//点一次
dp[i][m]=min(dp[i][m],dp[i][j]+1);//连点
}
}
for (int j=m-low[i];j>0;j--)//注意:0不能取(到地上就炸了
{
if (((Map[i-1])&&(j+low[i]>Mx[i-1]&&j+low[i]<Ms[i-1]))||!(Map[i-1]))//在范围内
dp[i][j]=min(dp[i][j],dp[i-1][j+low[i]]);//01背包的更新.往下掉
}
}
Min=INF;
for (int i=0;i<=m;i++) Min=min(Min,dp[n][i]);//求最小步数
for (int i=1;i<=n;i++)
{
if (Map[i-1]) flag=-1; else continue;
for (int j=0;j<=m;j++)
{
if (dp[i][j]!=INF)
{
flag=1;//标记过了这个管道
break;
}
}
if (flag==1) ans++; else break;
}
if (ans==k) printf("1\n%d",Min); else
printf("0\n%d",ans);
return 0;
}

P2038 无线网络发射器选址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var
d:integer;
q,w,max,n,i,j,zuo,you,shang,xia,fangan,ans:longint;
a,b,c:array[-2000..2000] of longint;//x对应a,y对应b,x是上下
lu,cun:array[-2000..2000,-2000..2000] of longint;

begin
readln(d);
readln(n);
for i:=1 to n do
begin
read(a[i],b[i],c[i]);
lu[a[i],b[i]]:=c[i];
end;
//write(lu[4,4],' ',lu[6,6],' ');
for i:=0 to 128 do
for j:=0 to 128 do
begin
zuo:=j-d;
you:=j+d;
shang:=i-d;
xia:=i+d;
//if (i=5) and (j=5) then write(zuo,' ',you,' ',shang,' ',xia,' ');
for q:=shang to xia do
begin
for w:=zuo to you do
cun[i,j]:=cun[i,j]+lu[q,w];//在内部的公共场所
//if cun[i,j]>cun[i-1,j-1] then ans:=cun[i,j];
end;
end;
ans:=-100;
for i:=0 to 128 do
begin
for j:=0 to 128 do
if cun[i,j]>ans then ans:=cun[i,j];
end;
for i:=0 to 128 do
for j:=0 to 128 do
if cun[i,j]=ans then inc(fangan);
write(fangan,' ',ans);
end.

P2296 寻找道路

将所有边倒过来来从终点往回搜看能否搜到。
然后从起点开始广搜,入队前先判断它所连的点是否能到达终点。
具体见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
int n,m;//n个点m条边
int e[200010],ee[200010];
int u[200010],v[200010];//边集数组
int uu[200010],vv[200010];//边集数组
int d[10010],dd[10010];//最后一个点位置。
int ff[10010];//标记是否可到达终点
int f[10010];//标记是否搜过。
struct he
{
int n;//编号
int s;//距离
}q[10010];
int s,t;//起点终点
int xx,yy,i,j;
int mmin,l,r;
void dfs(int i)
{
int j=i;
while (j!=-1)
{
if (ff[vv[j]]==0)//没搜过
{
ff[vv[j]]=1;//标记可以到达
dfs(dd[vv[j]]);//往下灌水
}
j=ee[j];
}
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)//初始化
{
d[i]=-1;
dd[i]=-1;
}
for (i=1;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
e[i]=d[u[i]];//存上一条边的位置
d[u[i]]=i;

uu[i]=v[i];vv[i]=u[i];//反过来。
ee[i]=dd[v[i]];//存上一条边的位置
dd[v[i]]=i;
}
scanf("%d%d",&s,&t);
ff[t]=1;
dfs(dd[t]);
//for (i=1;i<=n;i++) cout<<ff[i]<<endl;
if (ff[s]!=1)//起点无法到达终点
{
printf("-1\n");
return 0;
}
q[1].n=s;
q[1].s=0;//起点入队
l=0;
r=1;
mmin=-1;//初始化
f[s]=1;
while (l!=r)
{
l++;//队首出队
if (q[l].n==t)//找到了点t
{
if (mmin==-1) mmin=q[l].s;//找min
mmin=min(mmin,q[l].s);
continue;
}
i=d[q[l].n];//搜i连的所有边
while (i!=-1)
{
j=d[v[i]];
int f3=0;//标记用
while (j!=-1)//看与点v[i]相连的点是否都能到达终点,若都能,v[i]入队
{
if (ff[v[j]]!=1)
{
f3=1;//标记
}
j=e[j];
}
if (f3==1)//点v[i]有点不能到达终点
{
i=e[i];
continue;
}
if (ff[v[i]]==1&&f[v[i]]!=1)//可以到达终点,且没搜过。
{
f[v[i]]=1;//标记
r++;//入队
q[r].n=v[i];
q[r].s=q[l].s+1;
}
i=e[i];
}
}
cout<<mmin;//输出
return 0;
}

P2312 解方程

只能在大牛分站过的代码
读入的话模一个数
因为如果
ax+b=0
ax%k+b%k==0
为了避免奇怪的错误应该要多模几个数.
这里懒所以没有模多个数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
long long k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
k%=1000000007;
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int n,m,ans;
int b[1000010];
int a[200];
bool jie(int x)
{
long long sum=0;
for (int j=n;j>=1;j--)
{
sum=((sum+a[j])*(long long)x)%1000000007;
}
sum+=a[0];
return sum==0;
}//秦九韶优化
int main()
{
n=read();m=read();
for (int i=0;i<=n;i++) a[i]=read();
for (int i=1;i<=m;i++)//暴力
{
if (jie(i)) b[++ans]=i;
}
printf("%d\n",ans);
if (!ans) return 0;
for (int i=1;i<=ans;i++) printf("%d\n",b[i]);
return 0;
}

还是感觉这方法太假了,所以还是打个正常的吧
开始一直wa,然后发现是乘炸了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;

void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int mod[4]={0,22861,22907,22877};
int n,m,ans;
int b[1000010];
bool f[1000010];
int a[200][4];
void read(int d)
{
char s;
int base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')//读进来的数对于模每个数都要进行单独处理
{
for (int i=1;i<=3;i++)
a[d][i]=(a[d][i]*10%mod[i]+(s-'0'))%mod[i];
s=getchar();
}
for (int i=1;i<=3;i++) a[d][i]=a[d][i]*base;
}
bool jie(int x,int d)//求当x=x,模mod[d],是不是等于0
{
int sum=0;
for (int j=n;j>=1;j--)
{
sum=((sum+a[j][d])%mod[d]*x) % mod[d];
}
sum+=a[0][d];
sum%=mod[d];
return sum==0;
}
int heh;
int main()
{
scanf("%d %d",&n,&m);
for (int i=0;i<=n;i++) read(i);
for (int i=1;i<=m;i++)
{
if (f[i]) continue;//被标记了就不扫了
bool flag=true;
for (int j=1;j<=3;j++)
{
int I=i%mod[j];//取模防止乘炸
if (!jie(I,j)) //如果不等于0
{
flag=false;//标记i不是解
int X=I;
while (X<=m)//打标记
{
f[X]=true;
X+=mod[j];
}
}
}
if (flag) b[++ans]=i;
}
printf("%d\n",ans);
if (!ans) return 0;
for (int i=1;i<=ans;i++) printf("%d\n",b[i]);
return 0;
}