10.3 考试总结
Rosemary_dream · · 个人记录
T1
md考试的时候少打了个等号以为自己的算法假了。于是打了个错解。
直接记录每一个字符出现过没有，如果出现过，直接从上一个处理过的地方一路删到现在，只留找到的两个。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
map <char,bool> mp;
ll ans=0,tp=-1;
string s;
bool f;
int main()
{
// freopen("goodstr.in","r",stdin);
// freopen("goodstr.out","w",stdout);
cin>>s;
for(int i=1;i<s.size();i++){
if(mp[s[i]]){
ans=(ans-tp+i-1);
mp.clear();tp=-1;
if(i==s.size()-1) f=true ;
}
else {
mp[s[i]]=true ;
if(tp==-1) tp=i;
}
}
if(mp[s[s.size()]]==0&&(!f)) ans=(ans-tp+s.size());
printf("%lld\n",((s.size()-ans&1)?ans:ans+1));
fclose(stdin);
fclose(stdout);
return 0;
}
罪魁祸首：
if(tp=-1) tp=i;//就tm是你这少打了个等号T2
md怎么是推式子
先把式子摆上：
首先证明一下奇数的情况：
对于奇数来说， 如果想要找到一个与其不互质的数，那么一定要在其对应数位上放一个数（成为它的倍数），以此类推后，一定会有两个数互质（，所以在奇数情况下无论怎么排都会有
n! 种情况。
对于偶数来说，只有在奇数对偶位，偶数对奇位时才会出现
gcd=2 的情况，而奇对偶偶对奇的情况共有(n/2)!*(n/2)!=((n/2)!)^2 种，用总共的情况减去gcd=2 的情况就是gcd=1 的情况。因为剩下的都是至少有一个奇数对一个奇位的情况了。
再证一下为什么而奇对偶偶对奇的情况共有
(n/2)!*(n/2)!=((n/2)!)^2 种。对于每一种奇数排列，都会有相应的一整套偶位排列，而奇数排列共有
(n/2)! 种，偶位排列也有(n/2)! 种，所以共计((n/2)!)^2 种。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll n,ans=1,rdc=1;
int main()
{
// freopen("gcd.in","r",stdin);
// freopen("gcd.out","w",stdout);
scanf("%lld",&n);
for(int i=2;i<=n;i++) (ans*=i)%=mod;
if(n&1) return printf("%lld\n",ans),0;
else{
for(int i=2;i<=n/2;i++) (rdc*=(1LL*i*i))%=mod;
ans=(ans-rdc+mod)%mod;
}
printf("%lld\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
md就因为T1那些__想法，T2考试的时候没时间推了
T3
不想说啥了，直接暴力草过即可。
能减就减，不能减就加。直接
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans[1000001];
ll n,x,y,b,tot;
int main()
{
// freopen("recursion.in","r",stdin);
// freopen("recursion.out","w",stdout);
scanf("%lld%lld%lld%lld",&n,&b,&x,&y);
for(int i=1;i<=n;i++){
if(ans[i-1]<y) ans[i]=ans[i-1]+x;
else if(ans[i-1]>=y) ans[i]=ans[i-1]-y;
}
for(int i=1;i<=n;i++) tot+=ans[i];
printf("%lld\n",(tot+n*b));
fclose(stdin);
fclose(stdout);
return 0;
}T4
结论就是两个连续
#include<bits/stdc++.h>
using namespace std;
string c;int st=0,ed;
int sum=0,ans=0;
int main()
{
// freopen("knot.in","r",stdin);
// freopen("knot.out","w",stdout);
cin>>c;ed=c.size();
while(c[st]!='1') st++;
while(c[ed]!='1') ed--;
for(int i=st+1;i<=ed;i++){
if(c[i]=='1')
ans+=max(0,2-sum),sum=0;
else sum++;
}
printf("%d\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}