省选考前单挑做点ACM练练细节还是很不错的嘛～
福利：http://codeforces.com/gym/101350
先来放上惨不忍睹的virtual participate成绩（中间跑去食堂吃饭于是浪费了一点时间）
Problem A DNF
Problem B 1Y(5min)
Problem C 1Y(37min)
Problem D 2Y(9min)
Problem E 4Y(3h58min)
Problem F DNF
Problem G 1Y(4h13min)
Problem H 1Y(13min)
Problem I 1Y(1h7min)
Problem J 1Y(1h26min)
Problem K 1Y(2h36min)
Problem L DNF
Problem M 30Y(3h47min)
先来大体上说一下，整个5h都还算ok，然而这个M题。。。事故啊。。。（之后会说）
感觉这套题有点偏向化，思维量大代码量小，导致容易卡题，也容易柳暗花明。
下面就是题解啦～
Problem A:
这是一个很不错的思维题啊！
比较容易陷入误区的地方在于，这种三元集的题大部分人会先去考虑中间项，然而应该先考虑两边。
我们将1的个数前缀和一下，于是观察出如果(i,j,k)满足题意，那么presum[i]和presum[k]有一些奥妙重重的关系，
然后又发现一个惊人的事实：如果presum[i]和presum[k]满足的话，那么中间的j应该是有且仅有1个可能的，
这样就可以统计答案了。
时间复杂度O(n)，代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int N=;
int n, z[N], num=;
char c[N];
int64 calc ()
{
int64 ans=;
int cnt=;
for (int i=; i<(int)strlen(c); i++) if (c[i]=='') cnt++;
else z[++num]=cnt+, cnt=;
z[++num]=cnt+;
int64 a=, b=;
for (int i=; i<=num; i=i+) a+=z[i];
for (int i=; i<=num; i=i+) b+=z[i];
ans=a*b;
for (int i=; i<=num; i++) ans-=*z[i];
ans+=z[]+z[num];
ans+=num-;
return ans;
}
int main ()
{
int t, n;
scanf("%d", &t);
for (int i=; i<=t; i++)
{
scanf("%d%s", &n, c);
num=;
printf("%I64d\n", calc());
}
return ;
}
Problem B:
你会不会写程序呀～
你会不会比大小呀～
时间复杂度O(1)，代码如下：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while (T--)
{
int a,b;
cin>>a>>b;
if (b>a) cout<<"WeWillEatYou"<<endl; else cout<<"FunkyMonkeys"<<endl;
}
return ;
}
Problem C:
首先这个题有两问，
第一问的答案就是这n个数的总和，O(n)扫一下就好啦～
第二问的答案就是这n个数的最大公约数，O(n)扫一下也好啦～
时间复杂度O(n)，代码如下：
#include <bits/stdc++.h>
using namespace std;
int T,n;
int x[];
long long ans1,ans2;
int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
long long gcd(long long a,long long b)
{
if (b==) return a;
return gcd(b,a%b);
}
int main()
{
T=read();
while (T--)
{
n=read();
ans1=,ans2=;
for (int i=;i<=n;i++)
{
x[i]=read();
ans1+=x[i];
ans2=gcd(x[i],ans2);
}
cout << ans1 << ' ' << ans2 << endl;
}
return ;
}
Problem D:
首先很容易发现，不管怎么操作，大家的相对奇偶性是不变的。
然后发现所有数奇偶性相同是答案为yes的充要条件。（因为不可能小于0啊，如果小于0的话先大家都长高一下就好了～）
时间复杂度O(n)，代码如下：
#include <bits/stdc++.h>
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int T;
int h[];
int main()
{
cin>>T;
while (T--)
{
int n;
n=read();
for (int i=;i<=n;i++) h[i]=read();
bool check=true;
for (int i=;i<=n;i++) if (h[i]%!=h[]%) check=false;
if (check) cout <<"yes" << endl; else cout << "no" << endl;
}
return ;
}
Problem E:
这是个很有趣的题目呀～
大家千万不要被质数这个条件所迷惑啊，这题和这个一点关系也没有。
当n为偶数的时候，只需要先手取最中间两个，然后和后手对称取就能赢了，所以n>2且为偶数时，先手获胜。
当n为奇数的时候，只需要先手取最中间三个，然后和对手对称取就能赢了，所以n>3且为奇数时，先手获胜。
当n=1时，先手获胜。
当n=2时，先手只能取1，后手也取1，后手获胜。
当n=3时，先手只能取2，后手取1，后手获胜。
所以这个题只有n=2或者n=3的时候后手获胜，其他情况都是先手获胜。
自古博弈代码短～～～
时间复杂度O(1)，代码如下：
#include <bits/stdc++.h>
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int T,n;
int main()
{
T=read();
while (T--)
{
n=read();
if (n==||n==) cout << "second" << endl; else cout << "first" << endl;
}
return ;
}
Problem G:
这个题我是在比较靠后的时间去做的，
第一眼。。。smg。。。完全不会
第二眼。。。n和m这么大，连O(nm)都过不了。。。
第三眼。。。这个k怎么才20啊。。。这不是瞎容斥一下就好了。。。
我们枚举2^k种不同的情况，每个点能不能取，维护出x坐标最小最大值，y坐标最小最大值，剩下的全部数学手推即可。
时间复杂度O(2^k)，代码如下：
#include <bits/stdc++.h>
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
long long ans;
int T,n,m,k,minx,maxx,miny,maxy;
int x[],y[],path[];
void dfs(int x1,int cnt)
{
if (x1<=k)
{
dfs(x1+,cnt);
path[cnt+]=x1;
dfs(x1+,cnt+);
} else if (cnt>)
{
minx=,miny=;
maxx=,maxy=;
for (int i=;i<=cnt;i++)
{
int t=path[i];
minx=min(minx,x[t]);
maxx=max(maxx,x[t]);
miny=min(miny,y[t]);
maxy=max(maxy,y[t]);
}
long long r=1LL*minx*miny*(n-maxx+)*(m-maxy+);
if (cnt%==) ans-=r; else ans+=r;
}
}
int main()
{
T=read();
while (T--)
{
n=read(),m=read(),k=read();
for (int i=;i<=k;i++) x[i]=read(),y[i]=read();
ans=((1LL*n*(n-))/+n)*((1LL*m*(m-))/+m);
dfs(,);
cout << ans << endl;
}
return ;
}
Problem H:
这个题模拟一下就好了吧，先扫一遍字母，再扫一遍看一下是否回文。
时间复杂度O(n)，代码如下：
#include <bits/stdc++.h>
using namespace std;
int T;
string s;
bool deal(char x)
{
if (x=='A'||x=='H'||x=='I'||x=='M'||x=='O'||x=='T'||x=='U'||x=='V'||x=='W'||x=='X'||x=='Y') return false;
return true;
}
int main()
{
cin>>T;
while (T--)
{
cin>>s;
bool check=true;
for (int i=;i<s.length();i++) if (deal(s[i])) check=false;
for (int i=;i<s.length();i++) if (s[i]!=s[s.length()-i-]) check=false;
if (check) cout << "yes" << endl; else cout << "no" << endl;
}
return ;
}
Problem I:
这个题首先把符合条件的字母搞出来，然后我们枚举回文的中间点，往两侧扩展就行了。
然而回文串有奇数长度，有偶数长度不太好处理。
没关系，我们在每相邻的两个字母之间加一个"#"（任何从未出现的字符都可以），然后扫一下就行了。
（其实这道题最长回文子串可以Manacher做啊，O(n)就够了，然而并不需要QWQ。。。）
时间复杂度O(n^2)，代码如下：
#include <bits/stdc++.h>
using namespace std;
int T;
string s,ss;
bool deal(char x)
{
if (x=='A'||x=='H'||x=='I'||x=='M'||x=='O'||x=='T'||x=='U'||x=='V'||x=='W'||x=='X'||x=='Y') return false;
if (x=='#') return false;
return true;
}
int main()
{
cin>>T;
while (T--)
{
cin>>ss;
int n=ss.length();
s.clear();
s+="#";
for (int i=;i<n;i++)
{
s+=ss[i];
s+="#";
}
n=s.length();
int ans=;
for (int i=;i<n;i++)
{
int now=,tot=;
while (i-now->=&&i+now+<n&&s[i-now-]==s[i+now+]&&(!deal(s[i-now-]))) ++now;
for (int j=i-now;j<=i+now;j++) if (s[j]!='#') ++tot;
if (tot>ans&&(!deal(s[i]))) ans=tot;
}
cout << ans << endl;
}
return ;
}
Problem J:
看到这道题题目名字里面有个"physics"的时候吓坏我了一直不敢开，结果点进去一看。。。
初中老师说过～～～弓形面积＝扇形面积－三角形面积，
扇形面积会不会呀～
三角形面积会不会呀～
编程会不会呀（逃。。。）
时间复杂度O(1)，代码如下：
#include <bits/stdc++.h>
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int T,L,A;
double ans;
int main()
{
T=read();
while (T--)
{
L=read(),A=read();
ans=(double)A/*L*L*M_PI;
ans-=(double)0.5*L*L*sin((double)A/*M_PI);
printf("%.6lf\n",ans);
}
return ;
}
Problem K:
我们先暴力扫描出这个集合，然后暴力一下就好了。
时间复杂度O(n)，代码如下：
#include <bits/stdc++.h>
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int T,a,b,n;
int cnt[];
void deal(int n)
{
int t[];
memset(t,,sizeof(t));
while (n>)
{
++t[n%];
n=n/;
}
int ans=;
for (int i=;i<=;i++) ans=max(ans,t[i]);
for (int i=;i<=;i++) if (t[i]==ans) ++cnt[i];
}
int main()
{
T=read();
while (T--)
{
memset(cnt,,sizeof(cnt));
a=read(),b=read(),n=read();
for (int i=;1LL*i*i*a+1LL*b*i<=n;i++)
deal(1LL*i*i*a+1LL*b*i);
int ans=;
for (int i=;i<=;i++) if (cnt[i]>cnt[ans]) ans=i;
if (a+b>n) ans=-;
cout << ans << endl;
}
return ;
}
Problem M:
噩梦的一题。。。
我先写了个二分。。。然后我用的是cin。。。惨遭卡常。。。
于是写了个hash。。。惨遭卡常。。。
然后cin改成了scanf。。。WA了。。。
hash写跪了。。。终于过了。。。
时间复杂度O(n)，代码如下：
#include <bits/stdc++.h>
#define modp 100000007
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int T,c,n;
string s1;
double s2;
map<int,double> mp;
double a;
string r;
int hash(string &s)
{
long long ans=,now=;
for (int i=;i<s.length();i++)
{
ans=(107LL*ans+1LL*now*(s[i]-'A'+))%modp;
now=(17LL*now)%modp;
}
return ans%modp;
}
int main()
{
//freopen("M.in","r",stdin);
//freopen("M.out","w",stdout);
T=read();
while (T--)
{
c=read(),n=read();
mp.clear();
for (int i=;i<=c;i++)
{
char ch=getchar();
while ((ch<'a'||ch>'z')&&(ch<'A'||ch>'Z')) ch=getchar();
long long ans=,now=;
while (ch!=' ')
{
ans=(107LL*ans+1LL*now*(ch-'A'+))%modp;
now=(17LL*now)%modp;
ch=getchar();
}
scanf("%lf",&s2);
mp[ans%modp]=s2;
}
r="JD";
mp[hash(r)]=1.0;
double anss=0.0;
for (int i=;i<=n;i++)
{
scanf("%lf",&a);
char ch=getchar();
while ((ch<'a'||ch>'z')&&(ch<'A'||ch>'Z')) ch=getchar();
long long ans=,now=;
while (ch!='\n')
{
ans=(107LL*ans+1LL*now*(ch-'A'+))%modp;
now=(17LL*now)%modp;
ch=getchar();
}
anss+=a*mp[ans%modp];
}
printf("%.6lf\n",anss);
}
return ;
}
写完啦～撒花～