题目链接 A. Currency System in Geraldion
有1时，所有大于等于1的数都可由1组成。没有1时，最小不幸的数就是1.
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
void solve(){
int n,x;
scanf("%d",&n);
int flag = ;
for(int i = ; i<=n; i++){
scanf("%d",&x);
if(x == ) flag = ;
}
if(flag) printf("-1\n");
else printf("1\n");
}
int main()
{
solve();
return ;
}
神之队友，八个if条件秒A，orz...
最后给的两个矩形每个长和宽翻过来倒过去，有四种情况。再和给的第一个矩形匹配总共有八种情况。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
void solve(){
int a1,b1,a2,b2,a3,b3;
cin>>a1>>b1>>a2>>b2>>a3>>b3;
int flag = ;
if(a2+a3<=a1 && max(b2,b3)<=b1) flag = ;
if(a2+a3<=b1 && max(b2,b3)<=a1) flag = ;
if(a2+b3<=a1 && max(b2,a3)<=b1) flag = ;
if(a2+b3<=b1 && max(b2,a3)<=a1) flag = ;
if(b2+a3<=a1 && max(a2,b3)<=b1) flag = ;
if(b2+a3<=b1 && max(a2,b3)<=a1) flag = ;
if(b2+b3<=a1 && max(a2,a3)<=b1) flag = ;
if(b2+b3<=b1 && max(a2,a3)<=a1) flag = ;
if(flag) printf("YES\n");
else printf("NO\n");
}
int main()
{
solve();
return ;
}
题意：给定每一个字母出现的个数ai，组成一个最长的字母串.
此字母串满足的条件:
1.其中的每个字母出现的总次数不超过ai.
2.每个字母出现的次数必须是不同的。
题解：这个题直接贪心。 从最大值开始，拿第一组样例，2 5 5来说
排序后2 5 5，从最后5开始，找局部最优解。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[];
void solve(){
int n;
scanf("%d",&n);
for(int i = ; i<n; i++) scanf("%d",&a[i]);
sort(a,a+n);
int maxn = 1e9+;
long long sum = ;
for(int i = n-; i>=; i--){
if(maxn == ) break;
if(maxn>=a[i]){
sum += a[i];
maxn = a[i] - ;
}
else{
sum += maxn;
maxn--;
}
}
printf("%I64d\n",sum);
}
int main()
{
solve();
return ;
}
记得寒假做过这道水题，我发现我一见到做过的题就懵了。。。
就把第一个人票数一直和后面最大的比较，如果此人最大的小于后面最大的，他就再得一票，后面最大的那个就减一票，ans+1,排序，直到后面没有比它还大的。数据较小，不会超时，至于司老大说的二分法我还没有领会。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[];
void solve(){
int n,ans = ;
scanf("%d",&n);
for(int i = ; i<n; i++) scanf("%d",&a[i]);
while(){
sort(a+,a+n);
if(a[n-]<a[]) break;
a[n-]--;
a[]++;
ans++;
}
printf("%d\n",ans);
}
int main()
{
solve();
return ;
}
我想说这个题寒假也做过……
题意：对于每个人，他都想找到能和他组成最大力量的人匹配。
题解：所以从大到小排序后，我从最大值入手，找到后取出标记，再继续找下一个未被标记且最大的值，贪心思想。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = ;
int cnt[maxn][maxn];
int flag[maxn],ans[maxn];
struct node{
int x,y,v;
}arr[maxn*maxn];
bool cmp(node A,node B){
return A.v>B.v;
}
void solve(){
int n;
scanf("%d",&n);
int k = ;
for(int i = ; i<=n*; i++){
for(int j = ; j<i; j++){
scanf("%d",&cnt[i][j]);
arr[k].x = i;
arr[k].y = j;
arr[k].v = cnt[i][j];
k++;
}
}
sort(arr,arr+k,cmp);
for(int i = ; i<k; i++){
if(!flag[arr[i].x]&&!flag[arr[i].y]){
ans[arr[i].x] = arr[i].y;
ans[arr[i].y] = arr[i].x;
flag[arr[i].x] = ;
flag[arr[i].y] = ;
}
}
for(int i = ; i<*n; i++){
printf("%d ",ans[i]);
}
printf("%d\n",ans[*n]);
}
int main()
{
solve();
return ;
}
老柴一眼看出来这是道dfs题，可惜没时间做了。。。
题解：首先记录每个点的度数方便找到叶子节点。通过记录路上连续的猫的个数，判断是否走该点，然后继续遍历。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5+;
vector<int> path[maxn];
int cat[maxn],leaf[maxn];
int vis[maxn];
int n,m,num = ;
void dfs(int u,int numcat){
if(vis[u]) return;
else vis[u] = ;
if(cat[u]) numcat++;
else numcat = ;
if(numcat>m) return;//判断猫的数量是否超过m
if(leaf[u] == &&u != ) num++;//记录方案数
for(int i = ; i<path[u].size(); i++){
dfs(path[u][i],numcat);
}
}
void solve(){
scanf("%d%d",&n,&m);
for(int i = ; i<=n; i++) scanf("%d",&cat[i]);
int x,y;
for(int i = ; i<=n-; i++){
scanf("%d%d",&x,&y);
path[x].push_back(y);
path[y].push_back(x);
leaf[x]++;//寻找叶子节点
leaf[y]++;
}
dfs(,);
printf("%d\n",num);
}
int main()
{
solve();
return ;
}
找规律题目，这么多if else写的我醉醉的。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
void solve(){
int n,i = ,j = ,k = ;
scanf("%d",&n);
getchar();
char c;
for(int p = ; p<n; p++){
scanf("%c",&c);
if(c == 'B') i++;
else if(c == 'G') j++;
else if(c == 'R') k++;
}
if(i >= && j == && k == ) puts("B");
else if(i == && j >= && k == ) puts("G");
else if(i == && j == && k >= ) puts("R");
else if(i == && j == && k == ) puts("R");
else if(i == && j == && k == ) puts("G");
else if(i == && j == && k == ) puts("B");
else if(i > && j == && k == ) puts("GR");
else if(i > && j == && k == ) puts("GR");
else if(i == && j > && k == ) puts("BR");
else if(i == && j == && k > ) puts("BG");
else if(i == && j > && k == ) puts("BR");
else if(i == && j == && k > ) puts("BG");
else puts("BGR");
}
int main()
{
solve();
return ;
}
我还想说这个题寒假也做过。。。
唯一分解定理。即 : n = p1^e1* p2^e2 * p3^e3* … * pr^er;其中p为质数。
注意数据范围，所有素数乘起来便没有平方。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll p[];
void solve(){
ll n;
scanf("%I64d",&n);
int ans = ;
for(ll i = ; i*i<=n; i++){
if(n%i == ){
p[ans++] = i;
while(n%i == ){
n /= i;
}
}
}
if(n>) p[ans++] = n;
ll sum = ;
for(int i = ; i<ans; i++){
sum = sum*p[i];
}
printf("%I64d\n",sum);
}
int main()
{
solve();
return ;
}
I 和 G两个题还没看，未完待续。。。