注意特殊的输出格式：零多项式是一个特殊多项式，对应输出为0 0 0.0
输出的系数保留小数点后1位，舍入后为0.0，则不输出
意味着输出的数的绝对值至少都要大于0.05
#include
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
double c1[maxn],c2[maxn],ac[maxn];
int main(){
int n;
cin>>n;
int maxa=0;
for(int i=0;i>x>>y;
maxa=max(maxa,x);
c1[x]=y;
}
int m;
cin>>m;
int maxb=0;
for(int i=0;i>x>>y;
maxb=max(maxb,x);
c2[x]=y;
}
if(maxa=0;i--){
if(fabs(c1[i])>=0.05){
printf(" %d %.1lf",i,c1[i]);
}
}
printf("\n");
}
else{
int ans=0;
while(maxa>=maxb){
ac[maxa-maxb]+=c1[maxa]/c2[maxb];//同幂次累加
ans=max(ans,e);
double tmp[maxn];
for(int j=maxb;j>=0;j--){
int ee=e+j;
double cc=c*c2[j];
tmp[ee]=cc;
}
int mmax=0;
for(int j=maxa;j>=0;j--){
if(fabs(c1[j]-tmp[j])<0.05){
c1[j]=0.0;
continue;
}
else{
c1[j]-=tmp[j];
mmax=max(mmax,j);
}
}
maxa=mmax;
}
int cnt=0;
int mmax=0;
for(int i=ans;i>=0;i--){
if(fabs(ac[i])>=0.05){
cnt++;
mmax=max(mmax,i);
}
}
if(cnt==0){//特殊格式输出
printf("0 0 0.0\n");
}
else{
printf("%d",cnt);
for(int i=mmax;i>=0;i--){
if(fabs(ac[i])>=0.05){
printf(" %d %.1lf",i,ac[i]);
}
}
printf("\n");
}
cnt=0;
for(int i=maxa;i>=0;i--){
if(fabs(c1[i])>=0.05){
cnt++;
}
}
if(cnt==0){
printf("0 0 0.0\n");
}
else{
printf("%d",cnt);
for(int i=maxa;i>=0;i--){
if(fabs(c1[i])>=0.05){
printf(" %d %.1lf",i,c1[i]);
}
}
printf("\n");
}
}
return 0;
}
“我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性”
注意==“-0”==的情况，代表0为女性，所以不能简单的使用int输入，判断正负。
注意时间复杂度！无用数据不要管，只看对最终结果有影响的数据！
#include
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
vectorimg[maxn];
double sum[maxn][maxn];
int vis[maxn][maxn];
vectorans1,ans2;
int xb[maxn];
int check(string s){
int x;
if(s[0]=='-'){
x=stoi(s.substr(1));
xb[x]=-1;
}
else x=stoi(s),xb[x]=1;
return x;
}
int main(){
int n,m;
cin>>n>>m;
//存照片、性别
//不是所有照片都有用，只有s和t出现的照片才有用
for(int i=0;i>k;
for(int j=0;j>s;
x=check(s);
img[i].push_back(x);
vis[i][x]=1;//表示x出现在第i张照片上
}
}
int x,y;
string s,t;
cin>>s>>t;
x=check(s);y=check(t);
double mmax=0,mmay=0;
for(int i=0;i
L2-030 冰岛人 (25 分)
读题！读题！读题！
冰岛人姓名组成：名+姓（姓为其父亲的名+性别后缀）
普通人姓名组成：名+姓（姓只是单纯的姓氏+性别后缀）
“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。
意味着：如果a和b的公共祖先是c，c是a的第六代祖先，但却是b的第三代祖先，也属于五代以内存在公共祖先！
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
mapmp;//将名字转为数字
mapfa;//记录父辈
int xb[maxn];//性别
int vis[maxn];
int bx[maxn],by[maxn];//第几代
int check(string f,string s){//标记性别和其父辈
int l=s.size();
string name;
int flag;
if(s[l-1]=='m'||s[l-1]=='f'){//父辈未知
name=s.substr(0,l-1);
flag=(s[l-1]=='m')?1:-1;
}
else if(s[l-1]=='n'){
name=s.substr(0,l-4);
fa[f]=name;
flag=1;
}
else{
name=s.substr(0,l-7);
flag=-1;
fa[f]=name;
}
return flag;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
string fir,sec;
cin>>fir>>sec;
mp[fir]=i;
xb[i]=check(fir,sec);
}
int m;
cin>>m;
for(int i=0;i>m1>>x1>>m2>>x2;
if(xb[mp[m1]]*xb[mp[m2]]>0) puts("Whatever");
else if(mp[m1]==0||mp[m2]==0) puts("NA");
else{
memset(vis,0,sizeof(vis));
memset(bx,0,sizeof(bx));
memset(by,0,sizeof(by));
vis[mp[m1]]=1;
int cnt1=1,cnt2=1;
while(fa[m1]!=""){
x1=fa[m1];
int fx=mp[x1];
cnt1++;
bx[fx]=cnt1;
vis[fx]=1;
m1=x1;
}
int flag=0;
if(vis[mp[m2]]){//m2就是m1的祖先
flag=1;
}
else{
while(fa[m2]!=""){
x2=fa[m2];
int fx=mp[x2];
cnt2++;
by[fx]=cnt2;
if(vis[fx]){//公共祖先
if(by[fx]<5||bx[fx]<5){
flag=1;
break;
}
break;
}
vis[fx]=1;
m2=x2;
}
}
if(!flag) puts("Yes");
else puts("No");
}
}
return 0;
}
L2-034 口罩发放 (25 分)
1、身份z号唯一标识一个人
2、合法记录：身份z号必须是18位的数字（不是18位或者出现其他字符都不可以！）
3、“如果提交时间相同，则按照在列表中出现的先后顺序决定。”
sort的时候不能只比时间，还要比较出现顺序！！！
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
struct peo{
string name;
string id;
int pid;
int s;
int time;
}p[maxn];
mapmp,vis;
vectorans;
bool cmp(peo a,peo b){
if(a.time==b.time) return a.pid>d>>P;
for(int i=1;i<=d;i++){
int t,s;
cin>>t>>s;
int cnt=0;
for(int j=0;j>a>>b>>x;
scanf("%d:%d",&y,&z);
if(b.size()!=18) continue;//判断是否合法
int flag=0;
for(int i=0;i'9'){
flag=1;
break;
}
}
if(flag) continue;
p[cnt].pid=cnt;//出现顺序
p[cnt].name=a;
p[cnt].id=b;
p[cnt].s=x;
p[cnt].time=y*60+z;
if(p[cnt].s==1&&vis[p[cnt].id]==0){
ans.push_back(p[cnt]);
vis[p[cnt].id]=1;
}
cnt++;
}
sort(p,p+cnt,cmp);
int num=0;
for(int j=0;j=s) break;
if(mp[id]==0||(i-mp[id]>P)){
cout<
L1-002 打印沙漏 (20 分)
主要是根据等差数列求和公式来计算行数，不要直接计算（容易出错）
这样遍历，不会出错，而且数据也很小，不会T。
while(1){
//首项从3开始： 2*r*(r+2)+1>n
//首项从1开始，公差为2，利用等差数列求和公式na+n(n-1)/2：r*r-1>n,r--
if(2*(r+1)*(r+1)-1>n){//首项从1开始，利用奇数项求和公式(n+1)(a+nd)
break;
}
r++;
}
L1-006 连续因子 (20 分)
#include
using namespace std;
typedef long long ll;
int main(){
int n;
cin>>n;
int len=-1;
int ans=2;
for( l=2;l<=sqrt(n);l++){//如果写成l*l<=n，则要开long long，所以最好还是写成这样
if(n%l==0){
int m=n;
int r=l;
while(m%r==0){
m/=r;
r++;
}
if(len
L1-009 N个数求和 (20 分)
注意审题！
输入格式：
输入第一行给出一个正整数N（≤100）。随后一行按格式a1/b1 a2/b2 ...给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。
#include
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
int main(){
ll n;
scanf("%lld",&n);
ll fz,fm,g,lcm;
scanf("%lld/%lld",&fz,&fm);
for(int i=1;i0) cout<
L3-006 迎风一刀斩 (30 分)
1、无论如何旋转，形状不会发生改变，由于只旋转90、180或270，所以相邻点要么横坐标相等，要么纵坐标相等（除非该边是斜边）
2、一共4种切法
3+5 、 3+4 、 3+5 、4+4
4+4又可细分为两种情况：
1）平行于坐标轴切开，两矩形不存在斜边,只需看是否有一边边长相等即可
2）两梯形存在斜边：需考虑一种特殊情况–>斜边相等，直角腰不相等
#include
using namespace std;
struct point{
int x,y;
};
int main(){
int n;
cin>>n;
for(int i=0;i>k1;
vectorv1,v2;
for(int j=0;j>x>>y;
v1.push_back({x,y});
}
cin>>k2;
for(int j=0;j>x>>y;
v2.push_back({x,y});
}
if(k1+k2>8){ //非法情况
cout<<"NO\n";
continue;
}
if(k1==4&&k2==4){ //特殊情况
int l=0,w=0,a=0,b=0;
int cnt=0,z1=0,z2=0;
for(int j=0;jtmp;
if(k1
字符串题
L1-078 吉老师的回归 (15 分)
回想去年就是因为这道题有一个点一直过不了而痛失个人铜。。。
现在重新做题，也是发现了自己思维上的漏洞吧，果然还是自己实力有限。。。
#include
using namespace std;
const int maxn=1e3+10;
typedef long long ll;
string s[maxn];
int main()
{
int n,m;
cin>>n>>m;
getchar();
for(int i=0;im){//当前做题数为cnt+1，直接输出
cout<
L2-008 最长对称子串 (25 分)
暴力
#include
using namespace std;
int main(){
string s;
getline(cin,s);
int l=0;
int maxl=0;
for(int i=0;i=i;j--){
int l=i,r=j;
while(l<=r&&s[l++]==s[r--]){
if(l>r) maxl=max(maxl,j-i+1);
}
}
}
cout<
WA
#include
using namespace std;
int main(){
string s;
getline(cin,s);
int l=0;
int maxl=0;
while(ll) r--;
if(rj) maxl=max(maxl,r-l+1);
}
l++;
}
cout<
STL
L2-039 清点代码库 (25 分)
mapmp;
map默认按key值从小到大排序，因此vector会排好序
将map种的每对元素以pair的形式存入vector中，sort默认按pair的first从小到大进行排序
可将次数前加负号，也可重写cmp函数
(不知道为什么不能用map来写，一直有两个点过不去。。。)
#include
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
const int INF=0x3f3f3f3f;
typedef pair> p;
map,int>mp;
vectorans;
//bool cmp(const p &a,const p &b){
// if(a.first!=b.first) return a.first>b.first;
// for(int i=0;i>n>>m;
for(int i=0;iv;
for(int j=0;j>x;
v.push_back(x);
}
mp[v]++;
}
cout<,int>::iterator it1=mp.begin();
for(;it1!=mp.end();it1++){
ans.push_back(make_pair(-1*it1->second,it1->first));
}
sort(ans.begin(),ans.end());
//sort(ans.begin(),ans.end(),cmp);
vector::iterator it2=ans.begin();
for(;it2!=ans.end();it2++){
cout<<-1*it2->first;
for(int i=0;isecond.size();i++){
cout<<" "<second[i];
}
cout<
L3-002 特殊堆栈 (30 分)
vector在插入和删除的同时维护其升序状态
vector插入和删除时就按照大小顺序进行，避免每次重新排序
vector的妙用
//vector添加指定位置的元素（下标从0开始）
//在最前面的元素插入x
v.insert(v.begin(),x);
//在下标为2的元素前插入x
v.insert(v.begin()+2,x);
//在末尾插入x
v.insert(v.end(),x);
//vector删除指定元素
//删除下标为2的元素（第3个元素）
v.erase(v.begin()+2);
//删除一段元素
v.erase(v.begin()+1,v.begin()+5);
vector做法
#include
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
vectora;
stackst;
int main(){
int n;
cin>>n;
while(n--){
string s;
int x;
cin>>s;
if(s=="Pop"){
if(st.empty()) puts("Invalid");
else{
int tmp=st.top();
st.pop();
int k=lower_bound(a.begin(),a.end(),tmp)-a.begin();
a.erase(a.begin()+k);
cout<>x;
st.push(x);
int k=lower_bound(a.begin(),a.end(),x)-a.begin();
a.insert(a.begin()+k,x);
}
else{
if(st.empty()) puts("Invalid");
else{
int l=a.size();
int k=(l-1)/2;
cout<
线段树做法
线段树维护各正整数出现的次数，查找中值，即查询线段树上的第
(
c
n
t
+
1
)
/
2
(cnt+1)/2
(cnt+1)/2个值
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
struct node{
int l,r;
int cnt;//区间[l,r]中各数字出现次数之和
}tree[maxn<<2];
int st[maxn];
void bt(int root,int l,int r){
if(l==r){
tree[root].l=tree[root].r=l;
}
else{
tree[root].l=l;
tree[root].r=r;
int mid=(l+r)>>1;
bt(root<<1,l,mid);
bt(root<<1|1,mid+1,r);
}
}
void update(int root,int idx,int val){//单点修改
if(tree[root].l==tree[root].r){
tree[root].cnt+=val;
}
else{
int mid=(tree[root].l+tree[root].r)>>1;
if(idx<=mid) update(root<<1,idx,val);//注意区间判断，无需进行无效递归
else update(root<<1|1,idx,val);
tree[root].cnt=tree[root<<1].cnt+tree[root<<1|1].cnt;//更新当前结点的值
}
}
int query(int root,int num){//单点查询
if(tree[root].l==tree[root].r){
return tree[root].l;
}
if(tree[root<<1].cnt>=num) return query(root<<1,num); //左区间各数字出现次数就达到了num，那就只查询左区间，否则在右区间中找剩下的
else return query(root<<1|1,num-tree[root<<1].cnt);
}
int main(){
bt(1,1,maxn);//建树，维护结点表示的区间
int n;
cin>>n;
int num=0;
while(n--){
string s;
cin>>s;
if(s=="Pop"){
if(num==0) cout<<"Invalid\n";
else{
cout<>x;
st[++num]=x;
update(1,st[num],1);//入栈，将对应数字出现次数加1
}
else{
if(num<=0) cout<<"Invalid\n";
else{
int mid=(num+1)>>1;
cout<
搜索
DFS
L3-029 还原文件（30分）
#include
using namespace std;
const int maxn=2e5+10;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
typedef long long ll;
int n,m;
int H[maxn],k[maxn];
int h[110][maxn];
vectorans;
int vis[110];
void dfs(int idx){
if(ans.size()==m){
for(int i=0;i
L2-016 愿天下有情人都是失散多年的兄妹
每行给出以下信息：
本人ID 性别 父亲ID 母亲ID
本人性别明确，但其父母的性别未必明确（输入中可能根本不存在其父母的信息），所以需要手动补充父母的性别信息！！！便于后续的判断！
采集数据过程中注意数据的完整性！
#include
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
vectorp[maxn];
int xb[maxn];
int vis[maxn];
int flag;
void dfs(int x,int cnt){
if(flag) return;
if(cnt>5) return;
vis[x]=1;
for(int i=0;i>n;
for(int i=0;i>id>>s>>fa>>mo;
if(fa!=-1){
p[id].push_back(fa);
xb[fa]=1;//手动补充性别信息
}
if(mo!=-1){
p[id].push_back(mo);
xb[mo]=2;
}
if(s=='M') xb[id]=1;
else xb[id]=2;
}
int k;
cin>>k;
for(int i=0;i>x>>y;
if(xb[x]==xb[y]) puts("Never Mind");
else{
memset(vis,0,sizeof(vis));
flag=0;
dfs(x,1);
dfs(y,1);
if(!flag) puts("Yes");
else puts("No");
}
}
return 0;
}
L3-001 凑零钱 (30 分)
DFS+剪枝
如果所有钱加在一起都不够，那直接输出"No Solution"，否则最后一个测试点超时。
dfs里return的条件和剪枝条件注意先后顺序！！！
#include
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
int n,m;
vectormoney,ans;
int flag;
void dfs(int x,int sum){
if(flag) return;
if(sum==m){
flag=1;
for(int i=0;im) return;//对于x=n的判断不能放在sum=m的前面，有可能x=n时sum也恰好等于m，就会判错
ans.push_back(money[x]);
dfs(x+1,sum+money[x]);
ans.pop_back();
dfs(x+1,sum);
}
int main(){
cin>>n>>m;
ll sum=0;
for(int i=0;i>x;
sum+=x;
money.push_back(x);
}
if(sum
01背包变形
恰好装满
//dp[i][j]:前i枚硬币凑成不超过j元，最多选择几枚
//dp[i][j]=dp[i-1][j-a[i]]+1
#include
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
int dp[maxn];
int a[maxn];
int pre[maxn];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
memset(dp,-0x3f,sizeof(dp));//初始化为不可能取到的值
dp[0]=0;
dp[a[1]]=1;
pre[a[1]]=a[1];
for(int i=2;i<=n;i++){
for(int j=m;j>=0;j--){
if(j>=a[i]&&dp[j-a[i]]>=0){
if(dp[j-a[i]]+1>=dp[j]){//注意取等，更新路径
dp[j]=dp[j-a[i]]+1;
pre[j]=a[i];
}
}
}
}
if(dp[m]<=0){
cout<<"No Solution\n";
}
else{
vectorans;
while(m>=a[1]){
//cout<=0;i--){
cout<
L3-015 球队“食物链” (30 分)
DFS+剪枝
输入格式：
输入第一行给出一个整数N（2≤N≤20），为参赛球队数。随后N行，每行N个字符，给出了N×N的联赛结果表，其中第i行第j列的字符为球队i在主场对阵球队j的比赛结果：W表示球队i战胜球队j，L表示球队i负于球队j*，D表示两队打平，-表示无效（当i=j时）。输入中无多余空格。
输出格式：
按题目要求找到“食物链”T1 T2 ⋯ T**N，将这N个数依次输出在一行上，数字间以1个空格分隔，行的首尾不得有多余空格。若不存在“食物链”，输出“No Solution”。
1、剪枝优化：当剩余的所有球队都未战胜过第一支球队时，无需继续搜索。
2、注意题意：
L
L
L表示球队
i
i
i负于球队
j
j
j，即：球队
j
j
j战胜球队
i
i
i
#include
using namespace std;
typedef long long ll;
const int maxn=110;
int n,flag;
int vis[maxn],win[maxn][maxn];
vectorans;
void dfs(int x){
if(flag) return;
int f=0;
for(int i=1;i<=n;i++){ //剪枝操作
if(!vis[i]&&win[i][ans[0]]){
f=1;
break;
}
}
if(!f) return;
for(int i=1;i<=n;i++){
if(!vis[i]&&win[x][i]){
vis[i]=1;
ans.push_back(i);
if(ans.size()==n){
if(win[i][ans[0]]){ //找到的第一个答案就是字典序最小的答案。
flag=1;
return;
}
}
dfs(i);
if(flag) return;//已经找到答案，直接return
vis[i]=0;
ans.pop_back();
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
char ch;
cin>>ch;
if(ch=='W') win[i][j]=1;
else if(ch=='L') win[j][i]=1;
}
}
for(int i=1;i<=n;i++){ //vis无需每次清空，未找到答案，回溯到i时，之前被标记过的已经又全部被归0了
ans.push_back(i);
flag=0;
vis[i]=1;
dfs(i);
ans.pop_back();
vis[i]=0;
if(flag){
for(int j=0;j
BFS
L3-004 肿瘤诊断 (30 分)
三维BFS求连通块的面积（连通数目）
注意审题！！！
六个方向搜索
#include
using namespace std;
const int maxn=2e3+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
int m,n,l,t;
int num,flag;
int a[100][maxn][200];
int vis[100][maxn][200];
int dir[][6]={{0,-1,0},{0,0,1},{0,1,0},{0,0,-1},{1,0,0},{-1,0,0}};
struct node{
int x,y,z;
};
int bfs(int x,int y,int z){
queueq;
q.push({x,y,z});
int num=1;
while(!q.empty()){
node p=q.front();
q.pop();
for(int i=0;i<6;i++){
int dx=p.x+dir[i][0];
int dy=p.y+dir[i][1];
int dz=p.z+dir[i][2];
if(dx>=l||dx<0||dy>=m||dy<0||dz>=n||dz<0) continue;
if(a[dx][dy][dz]==0||vis[dx][dy][dz]) continue;
vis[dx][dy][dz]=1;
num++;
q.push({dx,dy,dz});
}
}
return num;
}
int main(){
cin>>m>>n>>l>>t;
int ans=0;
for(int i=0;i>a[i][j][k];
}
}
}
for(int i=0;i=t) ans+=num;
}
}
}
}
cout<
L3-008 喊山 (30 分)
第一想法DFS，但有两个测试点一直过不去
参考题解，重新读题，发现该题其实是分层的
如：
山头1和山头2临近
山头1和山头3临近
山头2和山头3临近
其实对于山头1来说，山头2和山头3的地位是一样的（属于同一层次），都是山头1可以直接呼叫到的。
这里并不存在两山头间距离远近的问题，dfs不适用
应该使用BFS，将各山头“分层”
#include
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
int n,m,k,q;
vectorv[maxn];
int vis[maxn],lev[maxn];
int mmax;
int ans;
void bfs(int x){
lev[x]=1;
vis[x]=1;
queueq;
q.push(x);
while(!q.empty()){
int y=q.front();
q.pop();
for(int i=0;i>n>>m>>k;
for(int i=0;i>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=0;i>q;
ans=0;
if(v[q].size()>0){
memset(vis,0,sizeof(vis));
mmax=0;
ans=INF;
vis[q]=1;
bfs(q);
}
cout<
L3-018 森森美图 (30 分)
6 6
9 0 1 9 9 9
9 9 1 2 2 9
9 9 2 0 2 9
9 9 1 1 2 9
9 9 3 3 1 1
9 9 9 9 9 9
2 1 5 4
选择图像上的两个像素点A和B，则连接这两个点的直线就将图像分为两部分
- 图像的左上角是坐标原点(0,0)，我们假设所有像素按矩阵格式排列，其坐标均为非负整数（即横轴向右为正，纵轴向下为正）。横轴为x,纵轴为y
- 忽略正好位于连接A和B的直线（注意不是线段）上的像素点，即不认为这部分像素点在任何一个划分部分上，因此曲线也不能经过这部分像素点。
- 曲线是八连通的（即任一像素点可与其周围的8个像素连通），但为了计算准确，某像素连接对角相邻的斜向像素时，得分额外增加两个像素分数和的2倍减一。例如样例中，经过坐标为(3,1)和(4,2)的两个像素点的曲线，其得分应该是这两个像素点的分数和(2+2)，再加上额外的(2+2)乘以(2−1)，即约为5.66。
题目种的曲线指的是从起点（像素点A到像素点B的曲线），这样的曲线一共有两条，直线AB的上方一条，直线AB的下方也有一条。曲线上的点，可由现在所在的点向八个方向扩散，只要最终能连接AB即可。但最终曲线上的所有点的分数和应该最小（最短路）。
利用叉乘判断点在直线的哪一边
#include
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
int a[110][110];
double dis[110][110];
int n,m;
int tag;//0:上半部分，1:下半部分
int dir[][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
struct Point{
int x,y;
bool operator !=(const Point &c) const{//c
return x!=c.x||y!=c.y;
}
}A,B;
int cross(Point a,Point b,Point p){//叉乘，判断点在直线的哪一边，等于0则在直线上
return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y);
}
void bfs(){
memset(dis,0x7f,sizeof(dis));//double不能直接memset成0x3f
queueq;
while(!q.empty()) q.pop();
q.push(A);
dis[A.x][A.y]=a[A.x][A.y];
while(!q.empty()){
Point p=q.front();
q.pop();
for(int i=0;i<8;i++){
int dx=p.x+dir[i][0];
int dy=p.y+dir[i][1];
Point next={dx,dy};
if(dx<1||dx>n||dy<1||dy>m) continue;
int f=cross(A,B,{dx,dy});
//包含起点和终点
if(tag==0&&next!=A&&next!=B&&cross(A,B,next)<=0) continue;
else if(tag&&next!=A&&next!=B&&cross(A,B,next)>=0) continue;
double num;
if(i<4) num=a[dx][dy]+dis[p.x][p.y];//上下左右方向
else num=(a[dx][dy]+dis[p.x][p.y])+(a[dx][dy]+a[p.x][p.y])*(sqrt(2)-1);//斜方向
if(dis[dx][dy]<=num) continue;
dis[dx][dy]=num;
if(dx==B.x&&dy==B.y){//已经达到终点，无需再将其入队，否则陷入死循环
continue;
}
q.push(next);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
cin>>A.y>>A.x>>B.y>>B.x;//注意坐标输入顺序
A.y++,A.x++,B.y++,B.x++;
double ans=0;
tag=0;bfs();ans+=dis[B.x][B.y];//上半部分
tag=1;bfs();ans+=dis[B.x][B.y];//下半部分
printf("%.2lf\n",ans-a[A.x][A.y]-a[B.x][B.y]);//起点和终点算了两次，需要减去
return 0;
}
链表
L2-022 重排链表 (25 分)
坑点：输入数据中可能会出现多余的无关结点（不在此链表上的结点、出现多个next为-1的结点）
最终链表结点个数，不一定就是题目所给的输入
n
n
n
#include
using namespace std;
const int maxn=1e6+10;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
typedef long long ll;
struct node{
int add;
int data;
int next;
}p[maxn];
vectorpre,las;
int main(){
int head,n;
scanf("%d%d",&head,&n);
for(int i=0;i=0&&j=0) printf("%05d %d -1\n",pre[i],p[pre[i]].data);
return 0;
}
数据结构
线段树
L3-017 森森快递 (30 分)
一条直线上的
N
N
N个城市，这些城市从左到右依次从0到
(
N
−
1
)
(N-1)
(N−1)编号；第
i
i
i号城市（
i
=
0
,
⋯
,
N
−
2
i=0,\cdots ,N-2
i=0,⋯,N−2）与第
(
i
+
1
)
(i+1)
(i+1)号城市中间往返的运输货物重量在同一时刻不能超过
C
i
C_i
Ci公斤。
现有
Q
Q
Q张订单，第
j
j
j张订单描述了某些指定的货物要从
S
j
S_j
Sj号城市运输到
T
j
T_j
Tj号城市。所有货物都有无限货源，不定时的挑选一定的货物进行运输，且中途不能卸货。
如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制，求出运输货物重量的最大值。
即：若选择订单
j
j
j，则运输的货物不能超过从
S
j
S_j
Sj到
T
j
T_j
Tj途径所有道路上运输限制的最小值
线段树维护区间最小值
由于运输货物的时间不定，任意时间都可以运输，所以可能出现某一条道路同时运输多个订单货物的情况。
如上图所示，如果在某一时刻选择从1到4运输重量为1的货物，则此时要选择从1到3运输货物，运输的货物重量也只能是1
也就是说每选取一个区间，就要将其所有子区间（途径的所有道路运输货物的重量）的值减去该区间的最小值（即修改区间最小值）。
而这就涉及到了区间修改的顺序问题，由于我们想让最终运输的货物重量尽可能地大，所以每次选择了一个区间之后，应该对尽可能少地区间产生影响。
区间顺序选择：
当区间左端点相同，我们应优先选择右端点小的区间（绿色的区间），不会对
[
R
1
,
R
2
]
[R_1,R_2]
[R1,R2]中的值产生影响。
>
当区间右端点相同，我们应优先选择左端点大的区间（绿色的区间），不会对
[
L
1
,
L
2
]
[L_1,L_2]
[L1,L2]中的值产生影响
注意求最小值时的初值：1ll<<60
赋成0x3f3f3f3f最后一个测试点过不了！
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const ll INF=1ll<<60;
struct node{
int l,r;
}p[maxn];
bool cmp(node a,node b){//区间排序
if(a.r==b.r) return a.l>b.l;
return a.r>tr[root].mix;
return;
}
int mid=(l+r)>>1;
bt(root<<1,l,mid);
bt(root<<1|1,mid+1,r);
push_up(root);
}
void push_down(int root){
if(tr[root].lazy){
tr[root<<1].lazy+=tr[root].lazy;
tr[root<<1].mix+=tr[root].lazy;
tr[root<<1|1].lazy+=tr[root].lazy;
tr[root<<1|1].mix+=tr[root].lazy;
tr[root].lazy=0;
}
}
void update(int root,int l,int r,int val){
if(tr[root].l>r||tr[root].r=l&&tr[root].r<=r){
tr[root].mix+=val;
tr[root].lazy+=val;
return;
}
push_down(root);
int mid=(tr[root].l+tr[root].r)>>1;
update(root<<1,l,r,val);
update(root<<1|1,l,r,val);
push_up(root);
}
ll query(int root,int l,ll r){
if(tr[root].l>r||tr[root].r=l&&tr[root].r<=r){
return tr[root].mix;
}
push_down(root);
ll ans;
int mid=(tr[root].l+tr[root].r)>>1;
ans=min(query(root<<1,l,r),query(root<<1|1,l,r));
return ans;
}
int main(){
int n,q;
cin>>n>>q;
bt(1,1,n-1);
for(int i=0;i>x>>y;
if(x>y) swap(x,y);
p[i].l=x;
p[i].r=y;
}
sort(p,p+q,cmp);
ll ans=0;
for(int i=0;i0) update(1,l+1,r,-num);//区间修改
}
cout<
树
1、按照题目所给定义建树：左子树键值大，右子树键值小
一边建树，一边维护层序
2、判断是否是完全二叉树
只需看层序遍历每个结点的序号是否满足从1到n，只要漏掉一个，都不是完全二叉树。
L3-010 是否完全二叉搜索树 (30 分)
#include
using namespace std;
const int maxn=1e3+10;
int a[maxn],vis[maxn];
maplev;
void bt(int root,int val){//建树
if(val>lev[root]){ //将当前值插入适应结点
int left=root<<1;
while(1){
if(lev[left]==0) {
lev[left]=val;
break;
}
if(val>lev[left]) left<<=1;
else if(vallev[right]) right<<=1;
else if(val>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
lev[1]=a[1];
for(int i=2;i<=n;i++){
bt(1,a[i]);
}
vectoridx;
map::iterator it=lev.begin();
vis[it->first]=1;
cout<second;
it++;
for(;it!=lev.end();it++){
vis[it->first]=1;
cout<<" "<second;
}
cout<
L3-016 二叉搜索树的结构 (30 分)
map中是否出现过key：
mp.count(key);
若存在，返回1，否则，返回0；
虽然说，map用[ ]访问不存在的key，value返回的是默认值（int为0，string为空串）
但是不知道为什么这道题，不能直接用mp[key]==0，来判，把这个改成count就对了。
#include
using namespace std;
const int maxn=1e3+10;
int a[maxn];
maplev,mp;
void bt(int root,int val){//建树
if(lev.count(root)==0){//遇到空结点，则赋值
lev[root]=val;
mp[val]=root;
return;
}
if(vallev[root]) bt(root<<1|1,val);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
bt(1,a[i]);
}
int m;
cin>>m;
while(m--){
int x,y;
string a;
cin>>x>>a;
if(a=="is"){
cin>>a>>a;
if(a=="root"){
if(mp[x]==1) cout<<"Yes\n";
else cout<<"No\n";
}
else if(a=="parent"){
cin>>a>>y;
if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";
else if(mp[y]/2==mp[x]) cout<<"Yes\n";
else cout<<"No\n";
}
else if(a=="left"){
cin>>a>>a>>y;
if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";
else if(mp[y]*2==mp[x]) cout<<"Yes\n";
else cout<<"No\n";
}
else if(a=="right"){
cin>>a>>a>>y;
if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";
else if(mp[y]*2+1==mp[x]) cout<<"Yes\n";
else cout<<"No\n";
}
}
else if(a=="and"){
cin>>y>>a>>a;
if(a=="siblings"){
if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";
else if(abs(mp[x]-mp[y])==1) cout<<"Yes\n";
else cout<<"No\n";
}
else if(a=="on"){
cin>>a>>a>>a;
if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";
else{
int c=mp[x],d=mp[y];
while(c!=0&&d!=0) c/=2,d/=2;
if(c==0&&d==0)cout<<"Yes\n";
else cout<<"No\n";
}
}
}
}
return 0;
}
堆的建立
L2-012 关于堆的判断 (25 分) 小顶堆
对输入字符串的巧妙处理–>输入格式已知
向上调整建堆
#include
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
mapmp;
int h[maxn];
int cnt;
void up(int x){
h[++cnt]=x;
int t=cnt;
while(t>1&&h[t/2]>h[t]){
swap(h[t/2],h[t]);
t/=2;//t>>=1
}
ans[t]=x;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
up(x);
}
for(int i=1;i<=n;i++){
mp[h[i]]=i;
}
getchar();
for(int i=0;i>x>>s;
if(s=="and"){
cin>>y>>s>>s;
if(mp[x]/2==mp[y]/2) puts("T");
else puts("F");
}
else if(s=="is"){
cin>>s>>s;
if(s=="root"){
if(mp[x]==1) puts("T");
else puts("F");
}
else if(s=="parent"){
cin>>s>>y;
if(mp[y]/2==mp[x]) puts("T");
else puts("F");
}
else if(s=="child"){
cin>>s>>y;
if(mp[x]/2==mp[y]) puts("T");
else puts("F");
}
}
}
return 0;
}
堆的基本 *** 作
push_heap( )函数
make_heap( ):生成一个堆，大顶堆或小顶堆
push_heap( ): 向堆中插入一个元素，并且使堆的规则依然成立
[点击参考此文章](make_heap()等函数的用法 - 阳离子 - 博客园 (cnblogs.com))
#include
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
mapmp;
int h[maxn];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>h[i];
push_heap(h + 1, h + 1 + i, greater());
}
for(int i=1;i<=n;i++){
mp[h[i]]=i;
}
getchar();
for(int i=0;i>x>>s;
if(s=="and"){
cin>>y>>s>>s;
if(mp[x]/2==mp[y]/2) puts("T");
else puts("F");
}
else if(s=="is"){
cin>>s>>s;
if(s=="root"){
if(mp[x]==1) puts("T");
else puts("F");
}
else if(s=="parent"){
cin>>s>>y;
if(mp[y]/2==mp[x]) puts("T");
else puts("F");
}
else if(s=="child"){
cin>>s>>y;
if(mp[x]/2==mp[y]) puts("T");
else puts("F");
}
}
}
return 0;
}
并查集
L3-003 社交集群 (30 分)
具有同一兴趣爱好的人归为一类，最终可归为几类，每类各有多少人。
#include
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
vectorp[maxn];
int fa[maxn];
int num[maxn];
seth;
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool cmp(int a,int b){
return a>b;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k;
scanf("%d:",&k);
for(int j=0;j::iterator it=h.begin();
for(;it!=h.end();it++){
int i=*it;
int x=p[i][0];
//将具有同一兴趣爱好的人加入同一集合中
for(int j=1;jans;
for(int i=1;i<=n;i++){
if(find(i)==i){//记录每个j
ans.push_back(num[i]);
}
}
cout<
图
L2-013 红色警报 (25 分)—连通块个数
DFS做法
被攻占的城市，不会再参与后续dfs找连通块中，所以不能只用一个vis来标记（vis每一次都会被全部清空），需要再借助另外一个标记！
#include
using namespace std;
const int maxn=1e3+10;
typedef long long ll;
vectorv[maxn];
int vis[maxn];//每次dfs时，标记是否已被访问过
int lost[maxn];//标记某城市是否已被攻占
int n,m;
vectorans;
void dfs(int x){
vis[x]=1;
if(x>=n) return;
for(int i=0;i>n>>m;
while(m--){
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
int cnt=0;//计算连通块个数
for(int i=0;i>k;
for(int i=0;i>x;
lost[x]=1;
memset(vis,0,sizeof(vis));
vis[x]=1;
int num=0;
for(int i=0;icnt) printf("Red Alert: City %d is lost!\n",x);
else{
printf("City %d is lost.\n",x);
}
cnt=num;
if(i==n-1){
cout<<"Game Over.\n";
}
}
return 0;
}
并查集做法
#include
using namespace std;
const int maxn=1e3+10;
typedef long long ll;
int n,m;
int fa[maxn];
int lost[maxn];
vector >road;
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int count(){
for(int i=0;i>n>>m;
for(int i=0;i>x>>y;
road.push_back({x,y});
}
int cnt=count();
int k;
cin>>k;
for(int i=0;i>x;
lost[x]=1;
int num=count();
//cout<<"num: "<cnt) printf("Red Alert: City %d is lost!\n",x);
else printf("City %d is lost.\n",x);
cnt=num;
if(i==n-1) puts("Game Over.");
}
return 0;
}
最短路问题
L2-001 紧急救援 (25 分) 单源最短路
Dij做法
#include
using namespace std;
const int maxn=1e3+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
int n,m,s,d;
int c[maxn];//cure
int e[maxn][maxn];//edge
int dis[maxn];//shortest
int vis[maxn];//visited
int cis[maxn];//max_num
int num[maxn];//the number of the shortest path
vectorpre[maxn];//path
vectorans;
void dfs(int x){
ans.push_back(x);
for(int i=0;icis[j]){
cis[j]=cis[u]+c[j];
pre[j].clear();
pre[j].push_back(u);
}
}
}
}
cout<=0;i--){
cout<<" "<>n>>m>>s>>d;
for(int i=0;i>c[i];
}
for(int i=0;i>u>>v>>h;
if(h
优先队列优化dij做法
#include
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef pair P;
struct edge{
int to,w;
};
vectore[maxn];
int c[maxn];
int dis[maxn];
int cis[maxn];
int vis[maxn];
int num[maxn];
vectorpre[maxn],ans;
int n,m,s,d;
void dfs(int x){
ans.push_back(x);
for(int i=0;i,greater >q;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
num[s]=1;
cis[s]=c[s];
q.push(P(0,s));
while(!q.empty()){
P a=q.top();
q.pop();
int u=a.second;
if(vis[u]) continue;
vis[u]=1;
for(int i=0;idis[u]+x.w){
dis[x.to]=dis[u]+x.w;
cis[x.to]=cis[u]+c[x.to];
num[x.to]=num[u];
q.push(P(dis[x.to],x.to));
pre[x.to].clear();
pre[x.to].push_back(u);
}
else if(!vis[x.to]&&dis[x.to]==dis[u]+x.w){
num[x.to]+=num[u];
if(cis[x.to]=0;i--){
cout<<" "<>n>>m>>s>>d;
for(int i=0;i>c[i];
}
for(int i=0;i>u>>v>>h;
//无向边！！！
e[u].push_back({v,h});
e[v].push_back({u,h});
}
dij();
return 0;
}
L3-005 垃圾箱分布 (30 分)
审清题意！！！
注意最值的初始化！！！
所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内(距离不大于D）。
如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。
因为垃圾箱最多只有十个，所以从每个垃圾箱出发，做dij
#include
using namespace std;
const int maxn=1e4+10;
#define INF 0x3f3f3f3f
typedef pair P;
int dis[maxn];
int e[maxn][maxn];
int vis[maxn];
int n,m,K,D,s;
mapmp;
int ans,des,ans_sum;
void dij(){
priority_queue,greater >q;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
q.push(P(0,s));
while(!q.empty()){
P a=q.top();
q.pop();
int u=a.second;
if(vis[u]) continue;
vis[u]=1;
for(int i=1;i<=n+m;i++){
if(!vis[i]&&dis[i]>dis[u]+e[u][i]){
dis[i]=dis[u]+e[u][i];
q.push(P(dis[i],i));
}
}
}
int mmin=INF;
int flag=1;
int sum=0;
for(int i=1;i<=n;i++){
if(dis[i]==INF||dis[i]>D){
flag=0;
break;
}
sum+=dis[i];
mmin=min(mmin,dis[i]);
}
if(flag){
if(anssum){
des=s;
ans_sum=sum;
}
else if(ans_sum==sum&&des>s){//平均距离最小的不唯一，则选序号小的
des=s;
}
}
}
}
int main()
{
cin>>n>>m>>K>>D;
des=n+m+1;
ans_sum=INF;
for(int i=1;i<=n+m;i++){
for(int j=1;j<=n+m;j++){
if(i==j) e[i][j]=0;
else e[i][j]=INF;
}
}
while(K--){
string a,b;
int u,v,w;
cin>>a>>b>>w;
if(a[0]=='G'){
u=n+a[1]-'0';
mp[u]=a;
}
else u=stoi(a);
if(b[0]=='G'){
v=n+b[1]-'0';
mp[v]=b;
}
else v=stoi(b);
if(w
L3-007 天梯地图 (30 分)
分别针对最短时间和最短距离进行dij
注意输出：
首先按下列格式输出最快到达的时间T和用节点编号表示的路线：
Time = T: 起点 => 节点1 => ... => 终点
然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：
Distance = D: 起点 => 节点1 => ... => 终点
如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。
而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。
如果这两条路线是完全一样的，则按下列格式输出：
Time = T; Distance = D: 起点 => 节点1 => ... => 终点
在求最快到达路线时，不能直接用之前求得的最短路来更新路径，因为最短路是按途径节点数最少来寻找最优解的，而求最快到达路线时的最短的那条并不一定是节点数最少的那条
#include
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
typedef pairP;
int n,m,s,t;
int dis[maxn];
int tis[maxn];
int vis[maxn];
int num[maxn];
struct edge{
int to;
int time;
int len;
};
vectore[maxn];
vectorpre[maxn],tre[maxn],ans1,ans2;
map,int>mp;
void dfs1(int x){
ans1.push_back(x);
for(int i=0;i,greater >p,q;
memset(dis,0x3f,sizeof(dis));
memset(tis,0x3f,sizeof(tis));
dis[s]=0;
p.push(P(0,s));
num[s]=1;
while(!p.empty()){
P a=p.top();
p.pop();
int u=a.second;
if(vis[u]) continue;
vis[u]=1;
for(int i=0;idis[u]+x.len){
dis[x.to]=dis[u]+x.len;
num[x.to]=num[u]+1;
p.push(P(dis[x.to],x.to));
pre[x.to].clear();
pre[x.to].push_back(u);
}
if(!vis[x.to]&&dis[x.to]==dis[u]+x.len){
if(num[x.to]>num[u]+1){//选择节点数少的那条路
pre[x.to].clear();
pre[x.to].push_back(u);
}
}
}
}
memset(vis,0,sizeof(vis));
int d[550];
tis[s]=0;
q.push(P(0,s));
while(!q.empty()){
P a=q.top();
q.pop();
int u=a.second;
if(vis[u]) continue;
vis[u]=1;
for(int i=0;itis[u]+x.time){
tis[x.to]=tis[u]+x.time;
d[x.to]=d[u]+x.len;
q.push(P(tis[x.to],x.to));
tre[x.to].clear();
tre[x.to].push_back(u);
}
else if(!vis[x.to]&&tis[x.to]==tis[u]+x.time){
if(d[x.to]>d[u]+x.len){//选择距离短的那条路（不能直接用前面的dis[]）
d[x.to]=d[u]+x.len;
tre[x.to].clear();
tre[x.to].push_back(u);
}
}
}
}
dfs1(t);
mp[ans1]=1;
dfs2(t);
if(mp[ans2]){//判断路径是否完全一样
cout<<"Time = "<=0;i--){
cout<<" => "<=0;i--){
cout<<" => "<>n>>m;
for(int i=0;i>u>>v>>o>>l>>tt;
if(o){
e[u].push_back({v,tt,l});
}
else{
e[u].push_back({v,tt,l});
e[v].push_back({u,tt,l});
}
}
cin>>s>>t;
dij();
return 0;
}
L3-011 直捣黄龙 (30 分)
选择合适的路径，以最快的速度占领敌方大本营。（最短路）
当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。（经过节点最多）
若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。（杀伤敌军最多）
注意路径不唯一时，条件的判断以及其他量的更新！！！
#include
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef pair P;
const int mod=1e9+7;
mapmp;
mappm;
int n,k,des;
string s,t;
int dis[maxn];
int vis[maxn];
int c[maxn];
int cis[maxn],num[maxn],sum[maxn];
struct node{
int to;
int w;
};
vectorv[maxn];
vectorpre[maxn],ans;
void dfs(int x){//输出路径
ans.push_back(x);
for(int i=0;i,greater >q;
memset(dis,INF,sizeof(dis));
dis[0]=0;
q.push(P(0,0));
cis[0]=0;
num[0]=1;
sum[0]=0;
while(!q.empty()){
P a=q.top();
q.pop();
int u=a.second;
if(vis[u]) continue;
vis[u]=1;
for(int i=0;idis[u]+x.w){//最短路
dis[x.to]=dis[u]+x.w;
cis[x.to]=cis[u]+c[x.to];
num[x.to]=num[u];
sum[x.to]=sum[u]+1;
pre[x.to].clear();
pre[x.to].push_back(u);
q.push(P(dis[x.to],x.to));
}
else if(dis[x.to]==dis[u]+x.w){
num[x.to]+=num[u];//更新最多路的数量
if(sum[x.to]=0;i--){
cout<<"->"<>n>>k>>s>>t;
mp[s]=0;
int cnt=1;
for(int i=1;i>name>>x;
if(!mp[name]){
mp[name]=cnt++;
}
pm[mp[name]]=name;
c[mp[name]]=x;
}
for(int i=0;i>a>>b>>w;
v[mp[a]].push_back({mp[b],w});
v[mp[b]].push_back({mp[a],w});
}
des=mp[t];
dij();
return 0;
}
计算几何
L3-021 神坛 (30 分)
从n个点中任选3个点，求其所形成的三角形面积的最小值。
1、利用叉乘计算三角形面积：
S
=
1
2
∣
A
B
⃗
×
A
C
⃗
∣
S=\frac{1}{2}|\vec{AB}\times\vec{AC}|
S=21∣AB
×AC
∣
2、级角排序
枚举点，该点可与其他所有点连边（形成向量），然后对所有向量按级角进行排序（顺时针或逆时针排序）；排好序之后，只有相邻的两个向量形成的三角形面积才可能是最小的。
参考：级角排序的方法：
1、利用atan2（）函数按极角从小到大排序
bool cmp1(point a,point b)
{
if(atan2(a.y,a.x)!=atan2(b.y,b.x))
return atan2(a.y,a.x)
2、利用叉积按极角从小到大排序
bool cmp2(point a,point b)
{
point c;//原点
c.x = 0;
c.y = 0;
if(compare(c,a,b)==0)//计算叉积，如果叉积相等，按照X从小到大排序
return a.x0;
}
3、先按象限从小到大排序 再按极角从小到大排序
int Quadrant(point a) //象限排序，注意包含四个坐标轴
{
if(a.x>0&&a.y>=0) return 1;
if(a.x<=0&&a.y>0) return 2;
if(a.x<0&&a.y<=0) return 3;
if(a.x>=0&&a.y<0) return 4;
}
bool cmp3(point a,point b) //先按象限从小到大排序 再按极角从小到大排序
{
if(Quadrant(a)==Quadrant(b))//返回值就是象限
return cmp1(a,b);//return cmp2(a,b)
else Quadrant(a)
注意要开long long
#include
using namespace std;
typedef long long ll;
const int maxn=5e3+10;
struct point{
ll x,y;
}p[maxn],q[maxn];
bool cmp(point a,point b){
return a.x*b.y-a.y*b.x>0;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&p[i].x,&p[i].y);
}
double mmin=1e18;
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=1;j<=n;j++){
if(i==j) continue;
q[cnt].x=p[j].x-p[i].x;
q[cnt++].y=p[j].y-p[i].y;
}
sort(q,q+cnt,cmp);//级角排序
for(int j=0;j
其他
L3-013 非常d的球 (30 分)
假设森森是一个质点，以森森为原点设立坐标轴，则森森位于(0, 0)点。
小球质量为w/100 千克（kg），重力加速度为9.8米/秒平方（m/s2）。
森森在地上用力d球的过程可简化为球从(0, 0)点以某个森森选择的角度an**g (0<an**g<π/2) 向第一象限抛出，抛出时假设动能为1000 焦耳（J）。
小球在空中仅受重力作用，球纵坐标为0时可视作落地，落地时损失p%动能并反d。
地面可视为刚体，忽略小球形状、空气阻力及摩擦阻力等。
求：最远的投掷距离，保留3位小数
被简单物理题难住。。。
求距离，那就需要知道速度和时间（s=vt)
假设以夹角
α
\alpha
α抛出,初速度为
v
0
v_0
v0,将其沿水平和竖直两个方向分解。
竖直方向：
只受重力，做匀减速运动（加速度为
g
g
g)，向上减速为0有：
v
0
s
i
n
α
=
g
t
v_0sin\alpha=gt
v0sinα=gt,则
t
=
v
0
s
i
n
α
g
t=\frac{v_0sin\alpha}{g}
t=gv0sinα
从抛出到第一次落地的总时间即为
T
=
2
t
=
2
v
0
s
i
n
α
g
T=2t=\frac{2v_0sin\alpha}{g}
T=2t=g2v0sinα
水平方向：
s
=
v
0
T
c
o
s
α
=
v
0
2
s
i
n
2
α
g
s=v_0Tcos\alpha=\frac{v_0^2sin2\alpha}{g}
s=v0Tcosα=gv02sin2α
当
α
=
π
4
\alpha=\frac{\pi}{4}
α=4π时，s取最大值，
s
=
v
0
2
g
=
2
E
k
m
g
s=\frac{v_0^2}{g}=\frac{2E_k}{mg}
s=gv02=mg2Ek
#include
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
int main(){
double w,p;
scanf("%lf%lf",&w,&p);
w/=100;
double s=0,Ek=1000,g=9.8;
while(Ek>=1e-9){//z
s+=2*Ek/(w*g);
Ek-=p*Ek/100;
}
printf("%.3lf\n",s);
return 0;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）