By shy
If we just ain't right, and it's time to say goodbye.
When it all falls down, when it all falls down.
————伪AK
1. 水题
在桌面上有一排硬币,共N枚,标号分别从1至N,每一枚硬币均为正面朝上。现在进行M次翻转操作,第i次翻转的规则是将标号为i的约数的硬币进行一次翻转。(正面向上的被翻转为反面向上,反之亦然)。求M次翻转后,正面朝上的硬币数量。
solution:
真*水题
可以按照题意模拟,对1-m中每个i枚举约数并相应翻转,O(M√M),随随便便就过。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
for(int j=1;j*j<=i;j++){
if(i%j==0){
if(j<=n) a[j]^=1;
if(i/j!=j&&i/j<=n) a[i/j]^=1;
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(!a[i]) ans++;
}
printf("%d\n",ans); |
然而实际上这道题完全可以用O(N)做出来,因为对于1-n中的每个编号i的硬币,翻转次数实际上为m/i,所以将翻转次数m/i%2即可判断硬币正反。
1 2 3 4 5 6 7
| scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
t[i]=m/i%2;
if(!t[i]) ans++;
}
printf("%d",ans); |
2. 虚无

solution:
真^水题x2
因为每种物品数量不限,所以m次全部选择代价最小的物品就可以了。
一朝被蛇咬,十年怕井绳,所以为了防炸浮点数,特意先将x*m再除y(然并卵)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| scanf("%d%d",&n,&m);
double mins=999999;//最小代价
int mx,my;//代价最小的xi和yi
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
double s=x*1.0/y;//算出一件物品的代价
if(s<mins){
mx=x;my=y;
mins=s;
}
}
mx*=m;//先将x*m再除y
printf("%.10lf",mx*1.0/my); |
3. 空洞
请求出第K小的数位和为10 的数。
solution:
1)答案最大在 10^7 级别,暴力枚举1-10^7的每个数,判断和是否为0,
1 2 3 4 5 6 7 8 9 10
| for(int i = 1; i <= 1e8; ++i){
if((i % 10) + (i / 10 % 10) + (i / 100 % 10) + (i / 1000 % 10) + ( i / 10000 % 10) + (i / 100000 % 10) + (i / 1000000 % 10) + (i / 10000000 % 10)== 10) {
//判断每一位加起来是否等于10
count ++;
if(count == k){
printf("%d",i);
break;
}
}
}//PS:挺简洁的,但是这代码看着有点<del>滑稽</del> |
另一种写法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| for(int i=1;i<=1e9;i++)
{
int k=i,Sum=0;
while(k!=0)
{
Sum+=k%10;
k/=10;
}//判断每一位加起来是否等于10
if(Sum==10) tot++;
if(N==tot){
printf("%d",i);
return 0;
}
} |
2)类似全排列,用搜索一位一位填数(昨天讲DFS,入戏太深……)
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
| int flag=1,k,ans=0;
int m=9;
int t[20];
void dfs(int n,int s){
if(n==0){
long long sum=0;
for(int i=1;i<=m;i++){
sum+=t[i];
}
if(sum==10) ans++;
if(ans>=k){
sum=0;
long long f=1;
for(int i=1;i<=m;i++){
sum+=t[i]*f;
f*=10;
}
printf("%lld\n",sum);
flag=0;
}
return;
}
for(int i=0;i<=9&&i<=10-s;i++){
t[n]=i;
dfs(n-1,s+i);
if(!flag) return;
}
}
int main(){
scanf("%d",&k);
dfs(m,0);
return 0;
}//多么<del>漂亮</del>的搜索模板……(逃 |
4. 荒诞

solution:
因为前缀的字典序随长度递增,所以前缀数组第i位的下标为i,即ANS=1~n的平方和(记得long long)。
1 2 3 4 5
| int len=strlen(s);
ll sum=0;
for(long long i=1;i<=len;i++)
sum=(sum+i*i)%mod;
printf("%lld\n",sum); |
5. 失意
小X 是一个实力不强的OIer,他一共在N 场比赛中失败过。
每一场比赛持续的时间可以用一个数轴上的区间[Li,Ri]来表示,同一时间可
能会有多场比赛。
退役后,小X 回忆起自己失败的OI 历程,他选择了M 场失败的比赛,定义
这M 场比赛持续时间的交集长度为这M 场比赛的失败程度。
小X 希望选出一组失败程度最高的M 场比赛。
4,5题Solution:
【2018常州】8-10 Day3
————But I'll be fine.