OP
\
A Alphabet Cookies
字符串处理
思路
统计字母数后比对，保证没有字母不足；
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,ap[26];
string g;
while(cin>>n)
{
memset(ap,0,sizeof ap);
cin>>g;
for(int i=0;g[i];i++)
{
ap[g[i]-'A']++;
}
int f=1;
cin>>g;
for(int i=0;g[i];i++)
{
ap[g[i]-'A']--;
if(ap[g[i]-'A']<0)f=0;
}
if(f)printf("Yes\n");
else printf("No\n");
}
return 0;
}
|
B Sequential game
模拟
思路
按要求模拟即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
string g;
while(cin>>g)
{
int zero=0,one=0;
if(g[0]=='1')one++;
else zero++;
for(int i=1;g[i];i++)
{
if(g[i]!=g[i-1])
{
swap(one,zero);
}
if(g[i]=='1')one++;
else zero++;
}
printf("%d %d\n",zero,one);
}
return 0;
}
|
C The Hardest Problem Ever
字符串处理
思路
按要求操作即可
思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
string g;
while(cin>>g)
{
if(g!="START")break;
getchar();
getline(cin,g);
for(int i=0;g[i];i++)
{
if(g[i]>='A'&&g[i]<='Z')
{
g[i]=(g[i]-'A'-5+26)%26+'A';
}
printf("%c",g[i]);
}
printf("\n");
cin>>g;
}
return 0;
}
|
D Dart game
dp
思路
建立两个dp空间，一个存储使用一倍，两倍和三倍的方案数，另一个存储只使用一倍和三倍的方案数；
这两个再作差即为目标分数的合法方案数，因为只要整个方案中存在使用过两倍的情况，便可以将这个两倍移至最后，方案即合法；
注意DP的细节，不可以在一次循环中同时dp一倍，二倍与三倍，推测是与后效性限制有关；
注：所有的可行值是1-20的1-3倍，和25的1-2倍，想玩的可以去洛圣都体验一下hhh；
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=2011;
int main()
{
int a[1100]={0},b[1100]={0};
a[0]=1,b[0]=1;
for(int k=1;k<=21;k++)
{
if(k==21)k=25;
for(int kk=1;kk<=3;kk++)
{
if(k==25&&kk==3)break;
for(int i=1;i<=1001;i++)
{
if(i>=k*kk)a[i]+=a[i-k*kk];
if(i>=k*kk&&kk!=2)b[i]+=b[i-k*kk];
a[i]%=M,b[i]%=M;
}
}
}
int n;
while(cin>>n&&n)
{
printf("%d\n",(a[n]-b[n]+M)%M);
}
return 0;
}
|
E Similar Word
字符串处理
思路
把一个串在后面加上自身后，循环对比即可；
如果两串长度不同则不可能为相似串；
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=2011;
int main()
{
string g,g1;
int a[26];
while(cin>>g)
{
cin>>g1;
int f=1;
if(g==g1)f=0;
g=g+g;
if(g.length()/2!=g1.length())f=0;
int i;
for(i=0;g1[i];i++)
{
if(!g.compare(i,g1.length(),g1))break;
}
if(!g1[i])f=0;
if(f)printf("yes\n");
else printf("no\n");
}
return 0;
}
|
F Post office
中位数
思路
特别像货仓选址问题；
在O(1)的时间复杂度内确定邮局的位置后，遍历区间求距离和，不会TLE；
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=2011;
int main()
{
int n;
ll pos[1003];
while(~scanf("%d",&n))
{
if(!n)break;
memset(pos,0,sizeof pos);
memset(frt,0,sizeof frt);
for(int i=1;i<=n;i++)
{
scanf("%lld",&pos[i]);
}
scanf("%d",&n);
int l,r;
while(n--)
{
scanf("%d%d",&l,&r);
ll ans=0;
for(int i=l;i<=r;i++)
{
ans+=abs(pos[i]-pos[l+r>>1]);
}
printf("%lld\n",ans);
}
}
return 0;
}
|
G Lucky Boy
几何，博弈
思路
首先确定好统计共线的方法；
对于任意两点，一定共线；
对于每一条直线，我们可以用斜截式定义并用map<pair<double,double>,int>储存，经测试，不存在斜率不存在的直线，无浮点误差影响（数据可加强）；
由规则来说，每次操作需要拿走共线的任意个点（≥1）也就是说，如果场上存在三点共线的情况，则a必赢；
如果不存在三点共线的情况，则此时的博弈即为以下状况：
场上存在n个点，a先手，每人次可以拿走1个或2个点，取走最后一个点者赢；
那么此时，如果场上有3n个点，则后手者可以控制使每次场上他拿完后仍剩余3n个点，即先手必输；
如果场上有3*n+1或3*n+2个点，则先手者可以取走1个或2个点，使场上剩余3*n个点，情况即变为先后手对换的上种情况，此时后手必输；
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=2011;
map<pair<double,double>,int>mp;
pair<ll,ll> p[1003];
int main()
{
int n;
while(~scanf("%d",&n))
{
mp.clear();
int i,j;
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&p[i].first,&p[i].second);
}
int ff=0;
for(i=1;i<=n&&!ff;i++)
for(j=i+1;j<=n&&!ff;j++)
{
{
double k=(p[j].second-p[i].second)*1.0/(p[j].first-p[i].first)
,b=p[i].second-k*p[i].first;
if(mp[{k,b}]==1)ff++;
mp[{k,b}]++;
}
}
if(ff||n%3)printf("a is the lucky boy.\n");
else printf("b is the lucky boy.\n");
}
return 0;
}
|
H Car race game
搜了一下题解，好像还要用到线段树之类的，感觉比较麻烦（懒），以后再来探索吧。
I Jiulianhuan
数学
思路
之前也没有玩过，赛后找了好多视频也没搞清楚怎么解的；
最后还是感谢sl大佬找的资料，如下：
来自知乎
高中数学书666；
注：题给数据有一些问题，1005的返回值应该是4260；
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=10007;
int qm(int a,int b)
{
int ans=1;
for(;b;b>>=1)
{
if(b&1)ans=ans*a%M;
a=a*a%M;
}
return ans;
}
int main()
{
int n;
while(cin>>n)
{
cout<<(qm(2,n+1)-2+(n&1)+M)*qm(3,M-2)%M<<endl;
}
return 0;
}
|
J The minimum square sum
打表，数学
思路
个人是ph大佬带我打表找规律，不过他要证一下，大家可以拭目以待hh；
结论可以从AC代码中直接读出来，在此不多赘述了；
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=2011;
int main()
{
ll n;
while(cin>>n)
{
if(n==2)printf("2\n");
else if((n+1>>1)&1)printf("%lld\n",n);
else printf("%lld\n",n*n*2);
}
return 0;
}
|
打表代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=2011;
int main()
{
int i,j,k;
for(i=3;i<=49;i+=2)
{
for(j=1;j<=200;j++)
{
for(k=j;k<=200;k++)
{
if((j*j+k*k)%i==0){printf("%d %d\n",i,(j*j+k*k));goto aa;}
else if((j*j+k*k)>i)break;
}
}
aa:
i=i;
}
return 0;
}
|
ED
实际上应该有一个 NEFU大一省赛训练3 的，但是那一场自己做得实在太水了，在此仅做标记。