首页 > 代码库 > BZOJ2900 好玩的数字游戏

BZOJ2900 好玩的数字游戏

2024-09-02 02:54:53   217人阅读

好玩的数字游戏

TK在虐题的同时，也喜欢玩游戏。
现在，有这样的一个游戏，规则是这样的：
先随机给出一个数字N，然后你在操场上把1到N的所有数字写成一排，就像这样：
123456789101112131415….
接着你在每个数字前面添上加减号，每逢排在奇数位上的数字，就写上加号；每逢排在偶数位上的数字，就写上减号。恩…最后你得到一个超级长的式子。并且可以算出这个式子的结果。
TK觉得这个游戏很有意思，于是他没日没夜地玩啊玩啊玩啊…
或许你觉得这个游戏没有意思…恩…但是，如果你是TK，对于给定的N，你能够算出来最后的结果应该是多少么？

输入格式：

多组数据。每个测试点的数据组数不超过1000组。
每一行仅一个正整数N。保证没有多余的什么奇怪的字符。
每个测试点的数据最后一行一定是数字0。代表这个测试点的结束。
 

输出格式：

对于每组数据，输出相应的结果。
 
 
大部分方法都是数位dp 我感到对奇偶性的分析不是很清晰 于是听到了czt的做法：：
对于一个K位长的数，在第J位上，数字为I 对最终结果的贡献，，
一个直观的规律 把I这个数在J位上删去以后 发现剩下的数位顺序写下的数字即是 它的项数 
另一个直观的规律 发现对于上面提到的状态 依次写下对答案的贡献以后 发现它是一个 公比为1 或者-1 的等比数列！！！
于是就可以使用数学方法完成这题了
 
ps： 这题还是关于奇偶的分析太蛋疼 大脑内存太小了 有没有什么方法能改进改进？？
 1 #include<cstdio>
 2 #define ll long long
 3 using namespace std;
 4 ll ans,n,pows[19];
 5 int main()
 6 {
 7     pows[0]=1; for(int i=1;i<=18;i++) 
 8         pows[i]=pows[i-1]*10;
 9     while(1) 
10     {
11         scanf("%lld",&n); if(n==0) return 0; 
12         for(int i=1;i<=9;i++)for(int j=0;j<=15;j++)for(int k=j;k<=15;k++)
13         {        
14             ll start,end,fr; 
15             if(pows[j]*i+(k>j)*pows[k]>n) continue; 
16             start=j==k?0:pows[k-1];
17             if(n>=pows[j]-1+pows[j]*i+pows[k+1]-pows[j+1]) end=pows[k]-1; 
18             else if(n%pows[j+1]/pows[j]<i) 
19                 end=n/pows[j+1]*pows[j]-1; 
20             else if(n%pows[j+1]/pows[j]==i) 
21                 end=n/pows[j+1]*pows[j]+n%pows[j]; 
22             else end=n/pows[j+1]*pows[j]+pows[j]-1; 
23             fr=(((i&1&&j==0&&(k&1)==0)^(k&1)^(j&1))*2-1)*i; 
24             if((k&1)==0&&j) 
25             {
26                 if(((start^end)&1)==0) ans+=fr;
27             } 
28             else ans+=(end-start+1)*fr;
29         }
30         printf("%lld\n",ans);ans=0;
31     }
32 }

 

 
 

BZOJ2900 好玩的数字游戏


联系
我们