250pt
數學模型：
給定一組數，求出現次數最多的數，若不唯一，取在數組中索引值的最大值最小的數。
分析：因為次要條件比較麻煩，數組周遊從末尾開始可輕易解決。
View Code
class ContestWinner
{
public:
int getWinner(vector <int> events)
{
int i,j,n,k,c,m=0;
k=0;
n=events.size();
for(i=n-1;i>=0;i--)
{
c=1;
for(j=i-1;j>=0;j--)
if(events[j]==events[i])
c++;
if(c>=m)
m=c,k=events[i];
}
return k;
}
}; 500pt
數學模型：
給定兩個矩形的坐标求相對關系。
分析：雖然解決了，但用的離散化矩陣的坐标，編寫起來比較麻煩還易錯。
别人做時直接用兩個一維區間相交的方法解決，相當漂亮。
結：方法可擴充到三維空間（長方體和長方體相交），甚至N維
View Code
class TwoRectangles
{
public:
string describeIntersection(vector <int> A, vector <int> B)
{
int x0,x1,y1,y0;
x1=max(A[0],B[0]);
y1=max(A[1],B[1]);
x0=min(A[2],B[2]);
y0=min(A[3],B[3]);
if(x1<x0&&y1<y0)
return "rectangle";
if(x1==x0&&y1<y0||x1<x0&&y1==y0)
return "segment";
if(x1==x0&&y1==y0)
return "point";
return "none";
}
}; 1000pt
數學模型：
求不大于N的含有count1個數字digit1和count2個數字digit2的數。
分析：
和SRM 545的550類似，都是給定一個數，求不大于它，符合一定條件的數。
都是從使用貪心+枚舉，從末尾開始枚舉數位來比對條件。
而此題有所不同的是有可能溢出，即所求的數的位數可能多于原數，剛開始做的時候想分類讨論，後來發現溢出的部分還要再分類，易錯，麻煩，怎麼寫自己都 不滿意，推倒重來；
後來猜想在數之前加入一些前導0來避開分類，處理時又易與數字中的0搞混，想解決又得分類，又不滿意，重想；
四天後又想到既然0會搞混，那加其它的不會搞混的就行了，于是改為加'-'，還真的解決了。
結：
這個算法可由2個數字推廣到10個數字。
解決滿足一定條件并不大于給定數的問題，都可以嘗試使用貪心+枚舉，從尾數位開始枚舉數字來比對條件。
View Code
class FavouriteDigits
{
public:
long long findNext(long long N, int digit1, int count1, int digit2, int count2)
{
int b[10]={0};
int i,j,k,n,t;
long long ret=0;
char s[33];
if(digit1>digit2)
swap(digit1,digit2),swap(count1,count2);
for(i=0;i<15;i++)
s[i]='-';
sprintf(s+i,"%lld",N);
for(;s[i]!='\0';i++)
b[s[i]-'0']++;
if(b[digit1]>=count1&&b[digit2]>=count2)
return N;
n=i;
for(i--;i>=0;i--)
{
if(s[i]=='-')
k=0;
else
{
k=s[i]-'0';
b[k]--;
}
for(k++;k<=9;k++)
{
b[k]++;
t=(b[digit1]>count1?0:count1-b[digit1])+(b[digit2]>count2?0:count2-b[digit2]);
if(t<=n-1-i)
break;
b[k]--;
}
if(k<=9)
break;
}
s[i]=k+'0';
for(i++;i<n-t;i++)
s[i]='0';
for(j=0;j<count1-b[digit1];j++)
s[i++]=digit1+'0';
for(j=0;j<count2-b[digit2];j++)
s[i++]=digit2+'0';
for(i=0;s[i]=='-';i++);
for(;s[i]!='\0';i++)
ret=ret*10+s[i]-'0';
return ret;
}
}; 轉載于:https://www.cnblogs.com/xchaos/archive/2012/06/28/2567013.html