DIV 2
1 250
十分無(wú)恥的一道題目，無(wú)恥的過(guò)掉
2 500
需要比較強(qiáng)的YY能力。
按照題目給出的思路，很顯然不能有進(jìn)位！然后數(shù)字只剩下了0 1 2 3；
我的第一反應(yīng)是這些東西，應(yīng)該是前面的某些數(shù)字的組合。。。(這個(gè)十分逼近答案了。。無(wú)語(yǔ)，然后卡住了)
既然只剩下了0123，很顯然的四進(jìn)制！我們算一下10^9次方范圍上，這樣的數(shù)究竟有多少個(gè)呢？2^18(0也算在內(nèi)了) 2^18這個(gè)數(shù)很小的！262144，然后逐個(gè)檢查吧！
看到這種low 和high數(shù)據(jù)范圍的題目往往讓人們想到數(shù)學(xué)解法。。怎么從數(shù)學(xué)中轉(zhuǎn)到計(jì)算機(jī)中，是一門能力啊！
long long S(long long N)
{
int ans=0;
while(N>0)
ans+=N%10,N/=10;
return ans;
}
class RabbitNumber
{
public:
int theCount(int low, int high)
{
int ans=0;
for(int i=0;i<(1<<18);i++)
{
long long x=0,y=i;
for(int j=0;j<9;j++){x=x*10+y%4;y/=4;}
if(x>=low&&x<=high && S(x*x)==S(x)*S(x))ans++;
}
if(high==1000000000)ans++;
return ans;
}
};
如果你是在沒(méi)有觀察出來(lái)，這個(gè)4進(jìn)制，也沒(méi)有關(guān)系，來(lái)看一下S(x)的性質(zhì)。如果x的數(shù)據(jù)范圍是10^9，那么S(x*x)是多大呢？ 9*18=162，然后S(x)的范圍就是sqrt(162)<13.我們枚舉數(shù)字之和小于等于14的數(shù)就完全OK。
那么數(shù)字之和小于等于14 的大概有多少呢？ 319770！ 也是一個(gè)相當(dāng)小的數(shù)！ 看一下wuyi大神的解法：
#define LL long long
const int limit = 14;
const int MaxN = 9;
int S, L,R;
int res;
int f(LL x) {
int ret=0;
while(x)ret+=x%10,x/=10;
return ret;
}
int Dfs(int d, LL x, int r) {
cout<<d<<" "<<x<<" "<<r<<endl;
if(x > R) return 0;
if(x >= L && x <= R) {
if((14-r)*(14-r) == f((LL)x * x)) ++ res;
}
for(int c = !d ; c < 10 && c <= r; ++ c)
Dfs(d + 1, x * 10 + c, r - c);
}
class RabbitNumber
{
public:
int theCount(int l, int r){
L=l;R=r;
res=0;
if(R == 1000000000) ++ res, -- R;
if(L > R) return res;
Dfs(0,0,14);
return res;
}
};
3 1000
很顯然純粹枚舉，當(dāng)然沒(méi)戲！但是有技巧的枚舉(剪枝)還是可以的！比如說(shuō)，純粹暴力數(shù)據(jù)是2^40,如果我們枚舉四個(gè)對(duì)角點(diǎn)，則數(shù)據(jù)范圍下降到了2^20！這種剪枝技巧實(shí)在是太強(qiáng)大了！
比如枚舉0 2 5 7
class CubeColoring
{
public:
long long theCount(vector <string> colors)
{
int n=colors[0].size();
long long res=0;
for(int a=0;a<n;a++)for(int c=0;c<n;c++)for(int f=0;f<n;f++)for(int h=0;h<n;h++)
{
if(colors[0][a]=='Y'&&colors[2][c]=='Y'&&colors[5][f]=='Y'&&colors[7][h]=='Y')
{
int B=0;for(int b=0;b<n;b++)if(b!=a&&b!=c&&b!=f&&colors[1][b]=='Y')B++;
int D=0;for(int d=0;d<n;d++)if(d!=a&&d!=c&&d!=h&&colors[3][d]=='Y')D++;
int E=0;for(int e=0;e<n;e++)if(e!=a&&e!=f&&e!=h&&colors[4][e]=='Y')E++;
int G=0;for(int g=0;g<n;g++)if(g!=c&&g!=f&&g!=h&&colors[6][g]=='Y')G++;
res +=B*D*E*G;
}
}
return res;
}
};
Test Case: 5
Succeeded: Yes
Execution Time: 604 ms
Args:
{{"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY"}}
Expected:
751325186912
Received:
751325186912
操作規(guī)模是2^27的，數(shù)據(jù)規(guī)模是一億三千萬(wàn)....TC還是蠻快的！
這個(gè)問(wèn)題的難點(diǎn)是怎么找到處理數(shù)據(jù)的方法，解法中就是把0 2 5 7單獨(dú)抽離，做枚舉！
整個(gè)DIV2的題目都是在處理數(shù)據(jù)范圍上下功夫！畢竟，這是coder的一個(gè)基本功！
================================================================================
不算華麗的分割線
================================================================================
DIV 1
0 250
通過(guò)DIV2 250
1 550
一樣的一個(gè)組合DP問(wèn)題，與SRM 478 rng58的那個(gè)dp組合問(wèn)題相似！以后再整理！
2 1000
沒(méi)看，以后再說(shuō)。。抓緊時(shí)間寫(xiě)作業(yè)。。。-_-~~~!!!!!!!!!好囧啊。。。