前言
由于自己是全机房唯一一个高一才开始学OI的人，老师又懒得教（不是，全靠自学苟活至今，学的东西不完整，所以自己上洛谷刷刷水题补一些基础的东西
说白了就是想摸鱼
P1012 拼数
因为每个数字的长度不同不好比较，所以要通过把数字组合起来考虑，这样它们的长度就是一样的
自己想的解法是一个一个把数字加到不同位置进行比较，类似于贪心，题解给的方法类似冒泡排序加贪心，若两个数正着放的结果小于倒着放的结果则交换位置。
记下这个题的原因是现在才知道string类型居然是可以加减的
#include<string>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
string a[25];int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)
if(a[i]+a[j]<a[j]+a[i])swap(a[i],a[j]);
for(int i=1;i<=n;i++)cout<<a[i];
}P1090 合并果子
记录一下优先队列的基本用法，具体可看Crloss的博客，好像这道题还可以用哈夫曼树的思想来理解
q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
priority_queue <int,vector<int>,greater<int> > q;//权值小的优先
//注意后面两个“>”不要写在一起，“>>”是右移运算符
priority_queue <int,vector<int>,less<int> >q;//权值大的优先
//实在不行写结构体，重载小于运算符，那么就是大的优先#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;int n;long long ans;
priority_queue<long long,vector<long long>,greater<long long> >q;
int main()
{
scanf("%d",&n);for(int i=1,a;i<=n;i++)scanf("%d",&a),q.push(a);
for(int i=1;i<n;i++)
{
long long a,b;
a=q.top();q.pop();
b=q.top();q.pop();
ans+=a+b;q.push(a+b);
}
printf("%lld\n",ans);
}P1803 凌乱的yyy / 线段覆盖
记得第一次我在考场上写的是树状数组优化dp，后来发现贪心爆简单。
按右端点排序后从左到右选取，遇到第一个可选的就选。这样子可以保证当前线段对后面选择的限制最小。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans,L[1000005],R[1000005],q[1000005];
bool cmp(int a,int b){return R[a]==R[b]?L[a]>L[b]:R[a]<R[b];}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&L[i],&R[i]),q[i]=i;
sort(q+1,q+1+n,cmp);
for(int i=1,r=-1;i<=n;i++)if(L[q[i]]>=r)r=R[q[i]],ans++;
printf("%d\n",ans);
}P1080 国王游戏
被高精度乘法教做人。。。。。。
考虑两个大臣i与j，把他们位置放入两个位置p1与p2(p1<p2)
设1到(p1-1)的大臣左手中的数的乘积为mul1,(p1+1)到(p2-1)的大臣左手的数乘积为mul2
把i放到p1,j放到p2他们得到金币的最大值为$max(\frac {mul1}{b_i},\frac {a_imul1mul2}{b_j})$
把j放到p1,i放到p2他们得到金币的最大值为$max(\frac {mul1}{b_j},\frac {a_jmul1mul2}{b_i})$
根据题意应该取最大值中较小的那个。
显然有$\frac {mul1}{b_i} \leq \frac {a_jmul1mul2}{b_i}$与$\frac {mul1}{b_j} \leq \frac {a_imul1mul2}{b_j}$
所以直接比较$\frac {a_imul1mul2}{b_j}$与$\frac {a_jmul1mul2}{b_i}$的大小就好了
如果$\frac {a_imul1mul2}{b_j} \leq \frac {a_jmul1mul2}{b_i}$就有$a_ib_i \leq a_jb_j$
这个时候应该把i放到p1,j刚到p2才能使最大值最小，又因为(p1<p2)，所以如果$a_ib_i \leq a_jb_j$,那么i应该放到j前面
直接按$a_ib_j$排序就好了，剩下的就交给高精度
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,A,B,a[1005],b[1005],q[1005];
struct node{int len,s[5005];}ans,sum;
bool cmp(int x,int y){return a[x]*b[x]<a[y]*b[y];}
node operator *(node a,int b)
{
for(int i=1;i<=a.len;i++)a.s[i]*=b;
for(int i=1;i<=a.len;i++)a.s[i+1]+=a.s[i]/10,a.s[i]%=10;
while(a.s[a.len+1])a.len++,a.s[a.len+1]+=a.s[a.len]/10,a.s[a.len]%=10;return a;
}
node operator /(node a,int b)
{
for(int i=a.len;i>=1;i--)a.s[i-1]+=a.s[i]%b*10,a.s[i]/=b;
while(a.len>1&&!a.s[a.len])a.len--;
return a;
}
bool operator <(node a,node b)
{
if(a.len!=b.len)return a.len<b.len;
for(int i=a.len;i>=1;i--)if(a.s[i]!=b.s[i])return a.s[i]<b.s[i];
return 0;
}
int main()
{
long long sum1=1;scanf("%d%d%d",&n,&A,&B);sum.len=1;sum.s[1]=1;sum=sum*A;sum1=A;
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),q[i]=i;
sort(q+1,q+1+n,cmp);
for(int i=1;i<=n;i++)
{
if(ans<sum/b[q[i]])ans=sum/b[q[i]];
sum=sum*a[q[i]];sum1*=a[q[i]];
}
for(int i=ans.len;i;i--)printf("%d",ans.s[i]);return 0;
}P1092 虫食算
永远学不会玄学剪枝暴力出奇迹的我。。。。。。
#include<cstdio>
#include<cstring>
#include <cstdlib>
int n,vis[30],num[30];char s[5][30];
int id(char a){return a-'A'+1;}
void dfs(int x,int y,int d)
{
if(x==0){if(d==0){for(int i=1;i<=n;i++)printf("%d%c",num[i],i==n?'\n':' ');exit(0);}return;}
for(int i=x-1;i>=1;i--)
{
int w1=num[id(s[1][i])],w2=num[id(s[2][i])],w3= num[id(s[3][i])];
if(w1==-1||w2==-1||w3==-1)continue;
if((w1+w2)%n!=w3&&(w1+w2+1)%n!=w3)return;
}
if(num[id(s[y][x])]==-1)
{
for(int i=n-1;i>=0;i--)if(!vis[i])
{
if(y!=3)
{
num[id(s[y][x])]=i;vis[i]=1;
dfs(x,y+1,d);
num[id(s[y][x])]=-1;vis[i]=0;
}
else
{
int w=num[id(s[1][x])]+num[id(s[2][x])]+d;
if(w%n!=i)continue;
num[id(s[y][x])]=i;vis[i]=1;
dfs(x-1,1,w/n);
num[id(s[y][x])]=-1;vis[i]=0;
}
}
}
else
{
if(y!=3)dfs(x,y+1,d);
else
{
int w=num[id(s[1][x])]+num[id(s[2][x])]+d;
if(w%n!=num[id(s[3][x])])return;
dfs(x-1,1,w/n);
}
}
}
int main()
{
scanf("%d%s%s%s",&n,s[1]+1,s[2]+1,s[3]+1);
memset(num,-1,sizeof num);dfs(n,1,0);
}