问题 A: 礼物

时间限制: 1.000 Sec  内存限制: 512 MB
提交 状态

题目描述

在一个n×n的网格图上，放置着m个礼物，每个礼物有一个价值vi(1≤i≤m)，你可以选择一个礼物，然后选择：
（1）取走与它同列的所有礼物，或者（2）取走与它同行的所有礼物
请问所能获取的礼物的最大价值之和是多少？

输入

第一行两个正整数n,m。
之后m行，每行三个整数xi,yi,vi，表示第i个礼物在第xi行,第yi列的格子上（不同礼物可能会在同一个格子），其价值为vi。

输出

一个整数，表示能获取的最大的礼物价值之和。

样例输入 Copy

6 7 
1 3 1 
2 2 2 
2 4 4 
3 3 6 
3 6 3 
5 2 5 
5 4 6

样例输出 Copy

11

提示

样例1解释

选择第5行的任意一个礼物，然后将第5行取完。
【数据范围】
对于40%的数据，1≤n,m≤100
对于70%的数据，1≤n,m≤1000，0<vi≤10000
对于100%的数据，1≤n≤1000，1≤m≤105，1≤xi,yi≤n，vi≤106

 这个题我就直接行列算了 然后比大小 应该有更简单的方法

但还是错了一次因为数据的范围问题。

#include<bits/stdc++.h>
using namespace std;
struct maap
{int x;int y;int v;
};
int main()
{int n,m;cin>>n>>m;maap a[m];long long x[n]={0},y[n]={0};for(int i=0;i<m;i++){cin>>a[i].x>>a[i].y>>a[i].v;}for(int i=0;i<m;i++){x[a[i].x]+=a[i].v;y[a[i].y]+=a[i].v;}sort(x,x+n);sort(y,y+n);long long maxx=max(x[n-1],y[n-1]);cout<<maxx<<endl;return 0 ;
}

 

问题 B: 数字游戏

时间限制: 1.000 Sec  内存限制: 512 MB
提交 状态

题目描述

有一天，小明给佳佳出了一道题，
给出一个正整数n，佳佳可以进行如下三种操作：
1、使n减去1
2、如果n是2的倍数，使n除以2
3、如果n是3的倍数，使n除以3
问佳佳最少可以通过几步操作，将n变为0。
为了考验佳佳的知识水平，小明给出了T个数字n1,n2,…,nT，让佳佳对每个数字都给出答案。然而佳佳一心只想着晚上吃啥，想让聪明的你来帮助他解决这个问题，并答应解决后请你吃饭，于是你义不容辞地接下了这个任务。

输入

第一行一个正整数T，表示总共有T个数字；
接下来T行，每行一个正整数ni

输出

共T行，每行一个数字，第i行为对于ni的答案。

样例输入 Copy

2 
7 
10

样例输出 Copy

4
4

提示

【样例解释】
7->6->2->1->0
10->9->3->1->0

【数据范围】
对于40%的数据，T≤10，ni≤30
对于70%的数据，T≤20，ni≤1000
对于100%的数据，T≤20，ni≤1000000

这个题当时是不会做的，下来之后又问了问同学才会做。底下就是我同学的代码了。

这个的思路如下：

先推出0，1，2，3到0需要的步数，很简单。

 下附我同学的代码

#include<bits/stdc++.h>
using namespace std;
int a[1000010]={0,1,2,2};
int main()
{for(int i=4;i<1000010;i++){int k=0x3f3f3f;if(i%2==0)k=min(k,a[i/2]);if(i%3==0)k=min(k,a[i/3]);k=min(k,a[i-1]);k=k+1;a[i]=k;}int t;cin>>t;while(t--){int n;cin>>n;cout<<a[n]<<endl;}return 0 ;
}

问题 E: 朋友

时间限制: 1.000 Sec  内存限制: 128 MB
提交 状态

题目描述

经过六年的努力，小明终于被一所知名中学录取。优秀的小明总是对一些奇奇怪怪的事情感兴趣，这次他想知道谁在这所新学校拥有的朋友最多，由于大家都才刚报到，所以小明只知道大家两两之间是否是朋友关系。 

输入

的第一行有两个整数n和m，n表示总人数，m表示总关系数。   
接下来n行，每行有2个以空格隔开的整数a和b，表示a和b是朋友，a和b均为1到n之间的整数。不会给出重复的朋友关系。 

输出

仅有一行，表示朋友数最多的人所拥有的朋友，每两个整数之间用空格隔开，按照字典序从小到大输出。如果存在多个人朋友数都是最多的情况，请输出字典序最小的那人的答案，具体见样例。 

样例输入 Copy

3 3 
1 2 
2 3 
1 3

样例输出 Copy

2 3

提示

1、2、3均拥有2个朋友，因此输出字典序较小的1的朋友即可。
1的朋友为2和3，按照字典序从小到大输出，数字之间用空格隔开。

50%的数据，1<=n<=10
80%的数据，1<=n<=1000
100%的数据，1<=n<=10000，m<=500000

这个题我好像没有用什么方法 不过我结束后查了看到了很多很简单的方法 这个好像是NOIP的原题 

我这个耗时很长 不要选择呜呜呜

#include<bits/stdc++.h>
using namespace std;
int n,m,j=0;
int b[10010]={0},d[10010]={0},a[1000010];
struct friends
{int f;int cnt;
}c[10010];
int cmp(friends a,friends b)
{if(a.cnt!=b.cnt){return a.cnt>b.cnt;}else{return a.f<b.f;}
}
int main()
{cin>>n>>m;for(int i=1;i<=2*m;i++){cin>>a[i];b[a[i]]++;}for(int i=1;i<=n;i++){c[i].f=i;c[i].cnt=b[i];}sort(c+1,c+n+1,cmp);for(int i=1;i<=2*m;i++){if(a[i]==c[1].f){if(i%2!=0){d[j++]=a[i+1];}else{d[j++]=a[i-1];}}}sort(d,d+j);for(int i=0;i<j;i++){cout<<d[i]<<" ";}return 0 ;
}

问题 G: 分数统计2

时间限制: 1.000 Sec  内存限制: 128 MB
提交 状态

题目描述

在统计完朋友情况之后，小明又对大家的毕业学校产生兴趣，但是他觉得单纯的统计人数是一件非常无聊的事情，于是他设计了一个算法，同一所学校毕业的学生，第1个将获得1分，第2个获得2分，第3个获得4分…，第i个将获得2i-1分，总分就是这所小学的得分，小明想知道得分最高的学校有多少分。

输入

第一行有两个整数n和m，n表示总人数，m表示已知的同校关系数量。
接下来n行，每行有2个以空格隔开的整数a和b，表示a和b是来自同一所学校，a和b均为1到n之间的整数。不会给出重复的信息。

输出

只有一行，为所有学校中的最高得分。最后得分可能会很大，你只需要输出后100位即可，不足100位的请直接输出。

样例输入 Copy

5 3
1 2
3 4 
1 3

样例输出 Copy

15

提示

1、2、3、4来自同一所学校，该所学校所得的分数为1+2+4+8=15

60%的数据，1<=n<=10
80%的数据，1<=n<=70
100%的数据，1<=n<=10000，1<=m<=100000

这个题当时是不会的 查了查是并查集的内容+高精度 现学现卖 我看的那个博客真的讲的好透彻  还要找几道并查集的练练 

 下附代码：

#include<bits/stdc++.h>
using namespace std;
int pre[10010],a[10010],m1;
int find(int x)
{if(pre[x]==0)return x;return pre[x]=find(pre[x]);
}
void join(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy){pre[fx]=fy;a[fy]+=a[fx];}m1=max(m1,max(a[fx],a[fy]));
}
int main()
{int n,m,x,y,k=0;cin>>n>>m;for(int i=1;i<=n;i++){a[i]=1;}for(int i=0;i<m;i++){cin>>x>>y;join(x,y);}int b[110]={0},c[110]={0};b[100]=1;c[100]=1;for(int i=2;i<=m1;i++){k=0;for(int j=100;j>=1;j--){b[j]=b[j]*2+k;k=b[j]/10;b[j]=b[j]%10;}k=0;for(int j=100;j>=1;j--){c[j]=b[j]+c[j]+k;k=c[j]/10;c[j]=c[j]%10;}}int q=1;while(c[q]==0&&q<100){q++;}for(int i=q;i<=100;i++){cout<<c[i];}return 0 ;
}

问题 I: 点牛

时间限制: 1.000 Sec  内存限制: 128 MB
提交 状态

题目描述

在农夫FJ(Farmar John)的农场中有成千上万头奶牛，庞大的牛群给FJ增添了很多麻烦，尽管他为每一头奶牛从1开始顺序编上了号码，但是在每天清晨点名时（确切的说是点牛），FJ还是常常被巨大的数字弄得头晕，比如： 
FJ：奶牛一亿两千三百四十五万九千九百九十九号！ 
Cow 123459999：到！ 
FJ：奶牛一亿两千三百四十……??? ……!@#$!@#$ 
你能帮助FJ解决这个问题吗？你只需要写一个程序，当FJ点到一头奶牛时，及时提醒他下一头奶牛的编号就可以了。^_^ 

输入

仅有一个整数：即FJ刚刚点过的奶牛的编号N。1 ≤ N ≤ 1050。

输出

快告诉FJ下一头奶牛的编号吧！

样例输入 Copy

3

样例输出 Copy

4

这个题我看到的时候觉得要用高精度 但我当时不会呜呜呜 所以我用了字符串 补了上面那道高精度的题之后好像懂了 等我明天试试用高精度写

下附代码：

#include<bits/stdc++.h>
using namespace std;int main()
{string s;cin>>s;int cnt=0;int l=s.size();for(int i=0;i<l;i++){if(s[i]=='9'){cnt++;}}if(s[l-1]=='9'){for(int i=l-1;i>=0;i--){if(s[i]=='9'){s[i]='0';}else{s[i]++;break;}}}else{s[l-1]++;}if(cnt==l){cout<<"1";}for(int i=0;i<l;i++){cout<<s[i];}return 0 ;
}

剩下的题还没补完 DP动态规划的题真的看不太懂 网上有解析也看不懂 好痛苦 明天争取把剩下的补完吧。