NOIP2019 pj备战计划-2

小菜

P1226【模板】快速幂||取余运算

本以为是道水题,没想到又踩坑了

卡在第六个点的TLE了,交了5遍才A掉。。。惨啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,P;
ll qaq (ll a,ll b,ll P)
{
if(b==0)return 1;
if(b%2==1)return qaq(a,b-1,P)*a%P;
if(b%2==0) return qaq(a,b/2,P)*qaq(a,b/2,P)%P;
}
int main()
{
scanf("%lld%lld%lld",&a,&b,&P);
printf("%lld^%lld mod %lld=%lld\n",a,b,P,qaq(a,b,P)%P);
}

杭电上A了为什么这里就不行呢?

看一下第六个点的数据:

1
2
in:2100000007 2100000089 45987 
out:2100000007^2100000089 mod 45987=4363

欧,把a先%一下P即可。。。so easy!

实际上。。。

是这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,P,p;
ll qaq (ll a,ll b,ll P)
{
if(b==0)return 1;
ll p=qaq(a,b/2,P);
if(b%2==0) return p*p%P;
if(b%2==1)return p*p*a%P;
}
int main()
{
scanf("%lld%lld%lld",&a,&b,&P);
printf("%lld^%lld mod %lld=%lld\n",a,b,P,qaq(a%P,b,P)%P);
}

想了一会,明白了:快速幂每次做了重复的两遍,没有必要。

我还是太菜了。。。


Task:pj试炼场2-2(续)

T4 P1086

一道看起来很难的题,但是,如果你仔细读题的话。。。

不是最优解!

只要模拟就行了,略带贪心

每次找最多的,看一下去了还来不来得及回来,如果有时间就去,没时间就直接回家

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
#include<bits/stdc++.h>
using namespace std;
int m,n,k;
int ans,t;
int fx,fy;
struct node
{
int x,y,num;
}f[500];// 行 列
bool cmp(node a,node b)
{
return a.num>b.num;
}
int main()
{
cin>>m>>n>>k;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>f[n*(i-1)+j].num;
f[n*(i-1)+j].x=i;
f[n*(i-1)+j].y=j;
}
}
sort(f+1,f+m*n+1,cmp);
fx=0;
fy=f[1].y;
for(int i=1;i<=m*n;i++)
{
t+=abs(f[i].x-fx)+abs(f[i].y-fy)+1+f[i].x;
if(t>k)
{
cout<<ans<<endl;
return 0;
}
t-=f[i].x;
ans+=f[i].num;
fx=f[i].x;
fy=f[i].y;
}
cout<<ans<<endl;
}

T5 P1098

大模拟,我更喜欢用队列(虽然不知道为什么),居然一遍就过了

还是没什么好说的

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
using namespace std;
int p1,p2,p3;
string a;
queue<char> q;
int main()
{
cin>>p1>>p2>>p3;
cin>>a;
for(int i=0;i<a.length();i++)
{
if(a[i]=='-'&&a[i+1]<='9'&&a[i+1]>='0'&&a[i-1]<='9'&&a[i-1]>='0'&&a[i-1]<a[i+1])
{
if(p1==3)
{
for(int k=(int)a[i-1]+1;k<=(int)a[i+1]-1;k++)
{
for(int j=1;j<=p2;j++)
{
q.push('*');
}
}
}
else
{
if(p3==1)
{
for(int k=(int)a[i-1]+1;k<=(int)a[i+1]-1;k++)
{
for(int j=1;j<=p2;j++)
{
q.push((char)k);
}
}
}
else
{
for(int k=(int)a[i+1]-1;k>=(int)a[i-1]+1;k--)
{
for(int j=1;j<=p2;j++)
{
q.push((char)k);
}
}
}
}
}
else
{
if(a[i]=='-'&&a[i+1]<='z'&&a[i+1]>='a'&&a[i-1]<='z'&&a[i-1]>='a'&&a[i-1]<a[i+1])
{
if(p1==3)
{
for(int k=(int)a[i-1]+1;k<=(int)a[i+1]-1;k++)
{
for(int j=1;j<=p2;j++)
{
q.push('*');
}
}
}
else
{
if(p1==1)
{
if(p3==1)
{
for(int k=(int)a[i-1]+1;k<=(int)a[i+1]-1;k++)
{
for(int j=1;j<=p2;j++)
{
q.push((char)k);
}
}
}
else
{
for(int k=(int)a[i+1]-1;k>=(int)a[i-1]+1;k--)
{
for(int j=1;j<=p2;j++)
{
q.push((char)k);
}
}
}

}
else
{
if(p1==2)
{
if(p3==1)
{
for(int k=(int)a[i-1]+1;k<=(int)a[i+1]-1;k++)
{
for(int j=1;j<=p2;j++)
{
q.push((char)(k-32));
}
}
}
else
{
if(p3==2)
{
for(int k=(int)a[i+1]-1;k>=(int)a[i-1]+1;k--)
{
for(int j=1;j<=p2;j++)
{
q.push((char)(k-32));
}
}
}

}
}
}
}
}
else
{
q.push(a[i]);
}
}
}
while(!q.empty())
{
cout<<q.front();
q.pop();
}
cout<<endl;
}

T6 P3952

混进来的蓝题

搞了半个下午才搞出来

其实题意还好理解,就是实现麻烦了点,细节处理上出了不少问题

看了题解才知道的

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
/*
句数
判断的
当前循环层数
复杂度
有没有中止

用过没
还在的变量
加复杂度

目前最大
循环数
*/

#include<bits/stdc++.h>
using namespace std;
string s1,s2,y;
int a1,a2,a3,a4,a5;
int vis[30],s[30],mark[200];
int T,m,n;
int main()
{
cin>>T;
while(T--)
{
a1=a2=a3=a4=a5=m=n=0;
memset(vis,0,sizeof(vis));
memset(mark,0,sizeof(mark));
do
{
s1=s2;
cin>>s2;
}
while(s2[0]!='O');
for(int i=0;i<s1.length();i++)
a1=(a1<<1)+(a1<<3)+s1[i]-'0';
for(int i=4;i<s2.length()-1;i++)
a2=(a2<<1)+(a2<<3)+s2[i]-'0';
while(a1>0)
{
a1--;
cin>>y;
if(y[0]=='F')
{
a3++;
cin>>y>>s1>>s2;
if(vis[y[0]-'a'])a3=-1;//重复
else
{
vis[y[0]-'a']=1;//已经用掉了
s[a3]=y[0]-'a';
}
if(s1[0]!='n'&&s2[0]=='n'&&a5==0)//数字+n
{
a4++;
mark[a3]=1;
}
else
{
if(((s1.length()==s2.length()&&s1>s2)||(s1.length()>s2.length())||(s1[0]=='n'&&s2[0]!='n'))&&a5==0)
{
a5=1;
n=a3;
}
}
}
else//E
{
vis[s[a3]]=0;
m=max(m,a4);//更新
if(mark[a3]==1)
{
a4--;
mark[a3]=0;
}
a3--;//跳出来
if(n>0&&n>a3)n=a5=0;//跳出来了n标记的循环
}
if(a3==-1)
{
cout<<"ERR\n";
a1=-1;
}
}
if(a3>0)
{
cout<<"ERR\n";
}
if(a3==0&&m==a2)
{
cout<<"Yes\n";
}
if(a3==0&&m!=a2)
{
cout<<"No\n";
}
}
}