JNU周练1013
CodeForces 337A
?給出n、m（n<=m）和m個數字，在m個數字中選n個數字，令這n個數字中最大數與最小數值差最小。
數據量小，直接暴力
#include?<iostream>#include?<algorithm>
using?namespace?std;
int?main()
{
????int?a[60],?n,?m;
????cin?>>?n?>>?m;
????for(int?i?=?0;?i?<?m;?i++)
????????cin?>>?a[i];
????sort(a,?a+m);
????int?min?=?1005;
????for(int?i=0;?i<=m-n;?i++)
????{
????????if(a[i+n-1]?-?a[i]?<?min)
????????????min?=?a[i+n-1]?-?a[i];
????}
????cout?<<?min?<<?endl;
????return?0;
}View Code?
?
CodeForces 337B
給出屏幕與電影的寬高比，電影按比例縮放，盡量占滿屏幕，求屏幕沒被占的面積的比例。輸出要求：分子分母互質。
?
找規律，無論是電影適應屏幕還是屏幕適應電影，得出的比例都是一樣的。同時注意兩比例相同時輸出0/1。
#include?<iostream>using?namespace?std;
int?gcd(int?x,?int?y)
{
????int?r;
????while(y!=0)
????{
????????r?=?x%y;
????????x?=?y;
????????y?=?r;
????}
????return?x;
}
int?main()
{
????int?a,?b,?c,?d,?temp;
????cin?>>?a?>>?b?>>?c?>>?d;
????a?=?a?*?d;
????c?=?c?*?b;
????if(a?<?c)??
????{
????????temp?=?a;
????????a?=?c;
????????c?=?temp;
????}
????c?=?a?-?c;
????temp?=?gcd(a,c);
????a?/=?temp;
????c?/=?temp;
????cout?<<?c?<<?"/"?<<?a?<<?endl;
????return?0;
}View Code?
CodeForces 337C
/*????題意：
????一人去參加比賽。每答對一題得一分。連續答對k題時先加一分然后總分數乘2然后連續答對題數歸0。
????然后給你題目總數n和他答對題目的個數m問你他能得的最低分是多少。
????要獲得最低分，要盡量避免連續答對k題，或者讓連續答對k題的情況盡量出現在分數少的時候
????方法是：設答對為1，答錯為0，以k-1個"1"和1個"0"為一組從后往前排列，
????最后得出兩部分，一部分是x組k-1個"1"和1個"0"，另一部分為連續y個1
????則n?=?k?*?x?+?y;??m?=?(k-1)?*?x?+?y;??--->?得?x?=?n?-?m
????第一部分好求：(k-1)?*?x
????第二部分需要找規律：
????另z?=?y?/?k，則有z*k次答對，取z?=?1,?2,?3,...總分數如下
????那么分數變化為：2*k,(2*k+k)*2,((2*k+k)*2+k)*2......。
????抽象出來這就是一個數列遞推公式為：a[z]=2*(a[z-1]+k)。
????展開移項后得：a[z]+2*k=2*(a[z-1]+2*k)。設c[z]=a[z]+2*k。那么c[z]/c[z-1]=2。等比數列。
????而c[0]=a[0]+2*k=2k。那么c[z]=2*k*2^z。所以a[z]=k*2^(z+1)-2*k。
? ? 數據大,要用到快速冪
*/
?注意中間數大，要開long long
#include?<iostream>using?namespace?std;
const?long?long?MOD?=?1000000009;
//計算a^bmodn?????
long?long?modexp_recursion(long?long?a,long?long?b,long?long?n)?????
{????
????long?long?t?=?1;
????if?(b?==?0)
????????return?1;
????if?(b?==?1)
?????????return?a%n;
????t?=?modexp_recursion(a,?b>>1,?n);
????t?=?t*t?%?n;
????if?(b&0x1)
????{????
????????t?=?t*a?%?n;
????}
????return?t;
?}?
int?main()
{
????long?long?n,?m,?k;
????cin?>>?n?>>?m?>>?k;
????long?long?a?=?m?/?(k-1);
????if(a?<=?n?-?m)
????????cout?<<?m?<<?endl;
????else
????{
????????long?long?ret?=?0;
????????a?=?n?-?(n-m)*k;
????????long?long?b?=?a?/?k;
????????if(b>0)
????????{
????????????//cout?<<?"b:"?<<?b?<<?endl;
????????????//cout?<<?modexp_recursion(2,?b,?MOD)?<<?endl;
????????????ret?=?2?*?k?*?modexp_recursion(2,?b,?MOD)?-?2*k;
????????????ret?=?ret?%?MOD;
????????????//cout?<<?"ret:"?<<?ret?<<?endl;
????????}
????????ret?=?(ret?+?(n-m)?*?(k-1))?%?MOD;
????????ret?=?(ret?+?(a-a/k*k))?%?MOD;
????????cout?<<?ret?<<?endl;
????????//cout?<<?"aaa:"?<<?modexp_recursion(2,100,MOD)?<<?endl;
????}
????return?0;
}View Code?
?
CodeForces 337D題意：給一棵n個結點的樹，任意兩個節點的距離是指連接兩點的最短的邊數
在樹上的某個結點有一個“惡魔之書”，這本書會讓距離它d以內的節點都受到影響已知有m個節點收到了影響，問最多有幾個結點可能放著“惡魔之書”？
?
據說是樹形dp，看題解知道大概思路后，自己寫代碼，挑了無數bug過了。。
規定點1為根節點?
dp[i][0] --- 代表節點 i 子樹中距 i 最遠的受影響點和 i 的距離。
dp[i][1] --- 上述的次遠距離
dp[i][2] --- 代表節點 i 子樹以外的部分?距 i 最遠的受影響點和 i 的距離。
若某點dp[i][0] 和 dp[i][2]均小于或等于影響范圍d，表示該點滿足條件。
?dp[i][0] 和 dp[i][1]好求，dp[i][2] 則要綜合(1) i 的祖先節點和(2)其父節點的其他子樹的情況。
?
狀態轉移方程：?
u（父）--- v（子）
fa(父) --- u, i (子)
dp[u][0] = max(dp[v][0] + 1)
dp[u][2] = ?max(dp[fa][2], {dp[fa][0] or dp[fa][1]} + 1) ??
?
#include?<iostream>#include?<cstring>
#include?<algorithm>
using?namespace?std;
#define?N?100010
#define?M?200010
int?head[N],?vid[N],?vis[N],?eNum,?n,?m,?d;
struct?Edge
{
????int?e;
????int?next;
}edge[M];
int?dp[N][3];
void?AddEdge(int?u,?int?v)
{
????edge[eNum].e?=?v;
????edge[eNum].next?=?head[u];
????head[u]?=?eNum++;
}
void?init()
{
????int?temp,?u,?v;
????eNum?=?0;
????memset(head,?-1,?sizeof(head));
????memset(vis,?0,?sizeof(vis));
????memset(dp,?-1,?sizeof(dp));
????cin?>>?n?>>?m?>>?d;
????for(int?i=1;?i<=m;?i++)
????{
????????cin?>>?temp;
????????vis[temp]?=?1;
????}
????for(int?i=1;?i<n;?i++)
????{
????????cin?>>?u?>>?v;
????????AddEdge(u,?v);
????????AddEdge(v,?u);
????}
}
void?dfs1(int?u,?int?fa)
{
????if(vis[u]==1)?dp[u][0]?=?0;
????for(int?i?=?head[u];?i?!=?-1;?i?=?edge[i].next)
????{
????????int?v?=?edge[i].e;
????????if(v?==?fa)?continue;
????????dfs1(v,?u);
????????if(dp[v][0]?+?1?>?dp[u][0])
????????{
????????????if(dp[v][0]!=-1)
????????????{
????????????????dp[u][1]?=?dp[u][0];
????????????????dp[u][0]?=?dp[v][0]?+?1;
????????????}
????????}
????????else?if(dp[v][0]?+?1?>?dp[u][1]?&&?dp[v][0]?!=?-1)
????????{
????????????dp[u][1]?=?dp[v][0]?+?1;
????????}
????}
}
void?dfs2(int?u,?int?fa)
{
????if(vis[u]==1?&&?dp[u][2]==-1)?dp[u][2]?=?0;
????for(int?i=head[u];?i?!=?-1;?i?=?edge[i].next)
????{
????????int?v?=?edge[i].e;
????????if(v?==?fa)?continue;
????????if(dp[u][2]!=-1)?dp[v][2]?=?dp[u][2]?+?1;
????????if(dp[v][0]+1?==?dp[u][0])
????????{
????????????if(dp[u][1]?!=?-1)
????????????????dp[v][2]?=?max(dp[v][2],?dp[u][1]+1);
????????}
????????else?if(dp[u][0]!=-1)
????????????dp[v][2]?=?max(dp[v][2],?dp[u][0]+1);
????????dfs2(v,?u);
????}
}
int?main()
{
????init();
????dfs1(1,?0);
????dfs2(1,?0);
????int?ans?=?0;
????for(int?i=1;?i<=n;?i++)
????????if(dp[i][0]<=d?&&?dp[i][2]<=d)
????????????ans++;
????//for(int?i=1;?i<=n;?i++)
????//{
????//????cout?<<?dp[i][0]?<<?"???"?<<?dp[i][1]?<<?"???"?<<?dp[i][2]?<<?endl;
????//}
????cout?<<?ans?<<?endl;
????return?0;
}
/*
9?4?3
1?2?8?9
1?5
5?4
4?3
3?2
5?6
6?7
7?8
8?9
*/View Code?
?
?CodeForces 337E
?題意，給你一顆n個數，構建一顆樹，包含所有數，滿足根結點等于兒子結點的乘積，并且所有葉子結點都是素數。
?
?
關鍵點：對每個a[i]分解質因子，得出因子個數。在此基礎上建樹，由于n<=8，所以直接dfs枚舉所有情況，得出最小的結點數。?
#include?<iostream>#include?<algorithm>
#include?<cstring>
using?namespace?std;
struct?Num
{
????long?long?b;
????int?c;
}num[10];
int?n;?//存輸入
int?a[80000],?index;
long?long?leftt[10];//標記剩余多少
int?vis[10],?sum,?ans_min;
int?prime(int?x)
{
????int?flag?=?0;
????for(int?i=2;?i*i<=x;?i++)
????{
????????if(x%i==0)
????????{
????????????flag?=?1;
????????????break;
????????}
????}
????if(flag)
????????return?0;
????return?1;
}
//篩選法求1000000內素數
int?prime1(int?x)
{
????int?flag?=?0;
????for(int?i=0;?a[i]*a[i]<=x;?i++)
????{
????????if(x%a[i]==0)
????????{
????????????flag?=?1;
????????????break;
????????}
????}
????if(flag)
????????return?0;
????return?1;
}
bool?cmp(Num?a,?Num?b)
{
????return?a.c?<?b.c;
}
void?dfs(int?t)
{
????//cout?<<?"t:?"?<<?t?<<?endl;
????if(t?==?n)
????{
????????int?ret?=?sum,?retn?=?n;
????????for(int?i=1;?i<=n;?i++)
????????{
????????????if(vis[i]!=0)
????????????{
????????????????ret?-=?num[i].c;
????????????????retn?--;
????????????}
????????}
????????if(retn>1)?ret++;
????????if(ret?<?ans_min)?ans_min?=?ret;
????????//------test
????????//if(ret==8)
????????//{
????????//????for(int?i=1;?i<=n;?i++)
????????//????{
????????//????????cout?<<?vis[i]<<endl;
????????//????}
????????//}
????????return?;
????}
????for(int?i=t+1;?i<=n;?i++)
????{
????????long?long?temp?=?leftt[i];
????????if(leftt[i]?>=?num[t].b?&&?leftt[i]%num[t].b==0)
????????{
????????????leftt[i]?/=?num[t].b;
????????????vis[t]?=?i;
????????}
????????dfs(t+1);
????????if(temp!=leftt[i])
????????{
????????????leftt[i]?*=?num[t].b;
????????????vis[t]?=?0;
????????}
????}
}
int?main()
{
????long?long?flag;
????index?=?0;
????for(int?i=2;?i<=1000;?i++)
????{
????????if(prime(i))
????????????a[index++]?=?i;
????}
????for(int?i=1001;?i<=1000000;?i++)
????{
????????if(prime1(i))
????????????a[index++]?=?i;
????}
????cin?>>?n;
????for(int?i=1;?i<=n;?i++)
????????cin?>>?num[i].b;
????for(int?i=1;?i<=n;?i++)
????{
????????num[i].c?=?0;?flag?=?num[i].b;
????????for(int?j=0;?j<index?&&?flag>1;?)
????????{
????????????if(flag%a[j]==0)
????????????{
????????????????flag?/=?a[j];
????????????????num[i].c?++;
????????????}
????????????else
????????????{
????????????????j++;
????????????}
????????}
????????//原數<=10^12，除遍10^6內的素數后，若該數仍大于0，則一定有且僅一個10^6+1~10^12的質因子
????????if(flag>1)?num[i].c++;
????}
????sort(num+1,?num+n+1,?cmp);
????sum?=?0,?ans_min?=?1000000000;
????memset(vis,0,sizeof(vis));
????for(int?i=1;?i<=n;?i++)
????{
????????leftt[i]?=?num[i].b;
????????sum?+=?num[i].c;
????????if(num[i].c!=1)?sum++;
????}
????//cout?<<?"sum:?"?<<?sum?<<?endl;
????dfs(1);
????cout?<<?ans_min?<<?endl;
????//for(int?i=1;?i<=n;?i++)
????//????cout?<<?num[i].b?<<?":?"?<<?num[i].c?<<?endl;
????//cout?<<?index?<<?endl;
????//cout?<<?a[index-1]?<<?endl;
????return?0;
}View Code?
?
?
轉載于:https://www.cnblogs.com/byluoluo/p/3369584.html
總結
- 上一篇： TQ210裸机编程(2)——LED流水灯
- 下一篇： 1cc等于多少mL？