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