热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Codechef_JULY14

感觉这套比赛题目比较容易,没有以前做过的某次codechef那么凶残。题目还是很有意思的,最好的是有中文翻译。CSUB:签到题࿰

感觉这套比赛题目比较容易,没有以前做过的某次codechef那么凶残。题目还是很有意思的,最好的是有中文翻译。

 

 

CSUB:签到题,直接从左往右扫一遍即可,维护前面出现过多少个1.

#include
#include

#define maxn 100100
using namespace std;char s[maxn];
long long ans;
int cur,T,n;int main()
{scanf(
"%d",&T);while (T--){scanf("%d%s",&n,s);ans=cur=0;for (int i=0; s[i]; i++)if (s[i]=='1') ans+=++cur;printf("%lld\n",ans);}return 0;
}

 

 

RETPO:简单找规律。注意一开始的朝向,同时根据对称性,所有的点都可以对称到第一象限来。要走弯路的话,第一个单位距离消耗3步,第二个单位距离消耗1步,第三个消耗3步,第四个1步,依次类推即可。

#include
#include

#include

using namespace std;long long x,y,n,ans;
int T;int main()
{scanf(
"%d",&T);while (T--){scanf("%lld%lld",&x,&y);if (x<0) x&#61;-x;if (y<0) y&#61;-y;n&#61;y-x;if (n>&#61;0 && n<&#61;1) ans&#61;x&#43;y;else {if (n<0) n&#61;-n;if (y>x) ans&#61;2*min(x,y)&#43;(n/2)*4&#43;(n&1)*1;else ans&#61;2*min(x,y)&#43;(n/2)*4&#43;(n&1)*3;}printf("%lld\n",ans);}return 0;
}

 

 

FROGV&#xff1a;氺题。对于每只青蛙&#xff0c;f[i]保存它向右最远可以传递到那一只青蛙&#xff0c;假设当前我们计算第i只青蛙&#xff0c;对于j>i&#xff0c;且i可以传递信息给j&#xff0c;那么f[i]&#61;max(f[j])。

#include
#include

#include

#include

#define maxn 100100
using namespace std;int g[maxn],f[maxn];
int n,m,k,x,y;struct node{int x,id;
}a[maxn];
bool cmp(node n1,node n2)
{
return n1.x<n2.x;
}
int main()
{scanf(
"%d%d%d",&n,&k,&m);for (int i&#61;1; i<&#61;n; i&#43;&#43;) scanf("%d",&a[i].x),a[i].id&#61;i;sort(a&#43;1,a&#43;1&#43;n,cmp);for (int i&#61;1; i<&#61;n; i&#43;&#43;) g[a[i].id]&#61;i;f[n]&#61;n;for (int i&#61;n-1; i>0; i--)if (a[i&#43;1].x-a[i].x<&#61;k) f[i]&#61;f[i&#43;1];else f[i]&#61;i;while (m--){scanf("%d%d",&x,&y);x&#61;g[x],y&#61;g[y];if (x>y) swap(x,y);if (y<&#61;f[x]) puts("Yes");else puts("No");}return 0;
}

 

 

SGARDEN&#xff1a;数学题。对于一种置换&#xff0c;它里面一定构成了若干个环。所有人都回到原地的步数就是所有环长度的lcm值。由于这个lcm值很大&#xff0c;必须对于每个环长度进行因数分解&#xff0c;保存每个质数出现的次数就可。最后取模计算。

#include
#include

#include

#include

#define maxn 100100
typedef
long long ll;
using namespace std;const int M&#61;1000000007;
int a[maxn],T,n,cur,N;
bool b[maxn];
ll ans;
map
<int,int> ss;void dfs(int x)
{
if (b[x]) return;cur&#43;&#43;,b[x]&#61;true;dfs(a[x]);
}
void deal(int x)
{
for (int i&#61;2; i*i<&#61;x; i&#43;&#43;){if (x%i) continue;N&#61;0;while (x%i&#61;&#61;0) x/&#61;i,N&#43;&#43;;ss[i]&#61;max(ss[i],N);}if (x>1) ss[x]&#61;max(ss[x],1);
}
int main()
{scanf(
"%d",&T);while (T--){ss.clear();ans&#61;1;scanf("%d",&n);for (int i&#61;1; i<&#61;n; i&#43;&#43;) scanf("%d",&a[i]),b[i]&#61;false;for (int i&#61;1; i<&#61;n; i&#43;&#43;)if (!b[i]){cur&#61;0;dfs(i);deal(cur);}for (int i&#61;2; i<&#61;n; i&#43;&#43;)while (ss[i]--) ans&#61;(ans*i)%M;printf("%lld\n",ans);}return 0;
}

 

 

DISHOWN&#xff1a;一看这个题目就是一个典型的并查集了。每次查找盘子的主人&#xff0c;然后两个主人之间的比较无非就是改变一下指针而已了&#xff0c;路径压缩&#xff0c;所有的操作都是O(1)的。

#include
#include

#include

#define maxn 10010
using namespace std;int a[maxn],f[maxn];
int n,q,T;int father(int x) { return f[x]&#61;&#61;x?f[x]:f[x]&#61;father(f[x]); }int main()
{
int ope,x,y;scanf("%d",&T);while (T--){scanf("%d",&n);for (int i&#61;1; i<&#61;n; i&#43;&#43;) scanf("%d",&a[i]),f[i]&#61;i;scanf("%d",&q);while (q--){scanf("%d",&ope);if (ope&#61;&#61;0){scanf("%d%d",&x,&y);x&#61;father(x),y&#61;father(y);if (a[x]&#61;&#61;a[y]){if (x&#61;&#61;y) puts("Invalid query!");continue;}if (a[x]>a[y]) f[y]&#61;x;else f[x]&#61;y;}else {scanf("%d",&x);printf("%d\n",father(x));}}}return 0;
}

 

 

LEPAINT&#xff1a;这个题目我一开始以为我会T。没想到写了一发最最暴力的居然都A掉了。不过我觉得这个应该是被卡掉的&#xff0c;只是数据不够强吧。优化可以是这样的&#xff0c;对于物品&#xff0c;直接预处理它染色多少次后&#xff0c;为某种颜色的概率。同时&#xff0c;后面的区间染色就用扫描区间的方法&#xff0c;直接得出&#xff0c;直接求和即可。对于题目所说的取子集的问题&#xff0c;就相当于在这个范围里面每一个物品都有0.5的概率被染色。

#include
#include

#include

using namespace std;double f[55][111],tmp[111],ans;
int L,R,n,m,c,T;int main()
{scanf(
"%d",&T);while (T--)//10
{scanf("%d%d%d",&n,&c,&m);for (int i&#61;1; i<&#61;n; i&#43;&#43;){for (int j&#61;0; j0;f[i][1]&#61;1;}while (m--)//50
{scanf("%d%d",&L,&R);for (int i&#61;L; i<&#61;R; i&#43;&#43;)//50
{for (int j&#61;0; j2,tmp[j]&#61;f[i][j];for (int j&#61;0; j//100for (int k&#61;0; k//100f[i][j*k%c]&#43;&#61;tmp[j]/c;}}ans&#61;0; for (int i&#61;1; i<&#61;n; i&#43;&#43;)for (int j&#61;0; jj;printf("%.9f\n",ans);}return 0;
}

 

 

GNUM&#xff1a;很好的一个题目。一开始我就看准了这个题目&#xff0c;花时间最多的一个题目。读完题目后直接想到的就是二分图取匹配。显然是T。可以建模来解。以a[i]b[j]且满足gcd条件的点为右点&#xff0c;连接汇点。中间是gcd出现过的质数&#xff0c;分别连接相应的左右点&#xff0c;所有的边流量都是1&#xff0c;跑最大流即可。这个做法肯定是没有错的。但是还是有一些问题存在。点太多了。咋解决&#xff1f;缩点&#xff0c;分别把左右边的点中含有相同的质因子种类的点缩成一个点&#xff0c;边容量累加。再跑最大流&#xff0c;缩点后&#xff0c;点数的级别也就1000吧&#xff0c;可以ac。

#include
#include

#include

#include

#include

#include

#define maxn 2002000
#define maxpri 100100
using namespace std;int pri[maxpri],pnum&#61;0,antipri[maxpri];
int z[1888][30],Z[1888],a[1888],aa[1888];
int to[maxn],c[maxn],next[maxn],first[maxn],edge,node;
int tag[maxn],d[maxn],Q[maxn],bot,top,TAG&#61;520;
int f[566666][30],Tf;
bool can[maxn];
int T,n,tmp,s,t,ans,cas;
map
<int,int> ss,pos,Ttime;//è´¨æ&#xfffd;°å¯¹åº&#xfffd;ç&#xfffd;&#xfffd;ç&#xfffd;¹ç&#xfffd;&#xfffd;ç¼&#xfffd;å&#xfffd;·int gcd(int A,int B) { return B&#61;&#61;0?A:gcd(B,A%B); }void getprim()
{
for (int i&#61;2; i){if (antipri[i]&#61;&#61;-1) continue;pri[&#43;&#43;pnum]&#61;i; antipri[i]&#61;pnum;for (int j&#61;i&#43;i; j1;}
}
int addnode()
{node
&#43;&#43;;first[node]&#61;-1;return node;
}
void _init()
{ss.clear(),pos.clear(),Ttime.clear();edge
&#61;-1,node&#61;0,Tf&#61;0;s&#61;addnode(),t&#61;addnode();ans&#61;0;
}
void addedge(int U,int V,int W)
{edge
&#43;&#43;;to[edge]&#61;V,c[edge]&#61;W,next[edge]&#61;first[U],first[U]&#61;edge;edge&#43;&#43;;to[edge]&#61;U,c[edge]&#61;0,next[edge]&#61;first[V],first[V]&#61;edge;
}
void deal(int x)
{Z[x]
&#61;0,tmp&#61;a[x],aa[x]&#61;tmp;for (int i&#61;1; pri[i]<&#61;tmp/pri[i]; i&#43;&#43;)if (tmp%pri[i]&#61;&#61;0){z[x][&#43;&#43;Z[x]]&#61;pri[i];while (tmp%pri[i]&#61;&#61;0) tmp/&#61;pri[i];}if (tmp>1) z[x][&#43;&#43;Z[x]]&#61;tmp;for (int i&#61;1; i<&#61;Z[x]; i&#43;&#43;)while (((aa[x]/z[x][i])%z[x][i])&#61;&#61;0) aa[x]/&#61;z[x][i];
}
void buildedge()
{
for (int x&#61;1; x<&#61;n; x&#43;&#43;)for (int y&#61;n&#43;1; y<&#61;n&#43;n; y&#43;&#43;)if (a[x]1){ int cur&#61;gcd(aa[x],aa[y]); if (pos[cur]) { Ttime[cur]&#61;Ttime[cur]&#43;1; continue; }pos[cur]&#61;&#43;&#43;Tf,f[Tf][0]&#61;0,Ttime[cur]&#61;1;for (int i&#61;1; i<&#61;Z[x]; i&#43;&#43;)if (aa[y]%z[x][i]&#61;&#61;0) f[Tf][&#43;&#43;f[Tf][0]]&#61;z[x][i]; f[Tf][f[Tf][0]&#43;1]&#61;cur;}for (int i&#61;1; i<&#61;Tf; i&#43;&#43;){int cur&#61;f[i][f[i][0]&#43;1],tc&#61;Ttime[cur],Nd&#61;addnode();//Nd为å½&#xfffd;å&#xfffd;&#xfffd;gcd代表ç&#xfffd;&#xfffd;ç&#xfffd;¹ã&#xfffd;&#xfffd;
addedge(s,Nd,tc);for (int j&#61;1; j<&#61;f[i][0]; j&#43;&#43;){if (ss[f[i][j]]&#61;&#61;0) ss[f[i][j]]&#61;addnode();addedge(Nd,ss[f[i][j]],tc);}}pos.clear(),Tf&#61;0;for (int x&#61;1; x<&#61;n; x&#43;&#43;)for (int y&#61;n&#43;1; y<&#61;n&#43;n; y&#43;&#43;)if (a[x]>a[y] && gcd(aa[x],aa[y])>1){ int cur&#61;gcd(aa[x],aa[y]);if (pos[cur]) { Ttime[cur]&#61;Ttime[cur]&#43;1; continue; }pos[cur]&#61;&#43;&#43;Tf,f[Tf][0]&#61;0,Ttime[cur]&#61;1;for (int i&#61;1; i<&#61;Z[x]; i&#43;&#43;)if (aa[y]%z[x][i]&#61;&#61;0) f[Tf][&#43;&#43;f[Tf][0]]&#61;z[x][i];f[Tf][f[Tf][0]&#43;1]&#61;cur;}for (int i&#61;1; i<&#61;Tf; i&#43;&#43;){int cur&#61;f[i][f[i][0]&#43;1],tc&#61;Ttime[cur],Nd&#61;addnode();//Nd为å½&#xfffd;å&#xfffd;&#xfffd;gcd代表ç&#xfffd;&#xfffd;ç&#xfffd;¹ã&#xfffd;&#xfffd;
addedge(Nd,t,tc);for (int j&#61;1; j<&#61;f[i][0]; j&#43;&#43;){if (ss[f[i][j]]&#61;&#61;0) continue;addedge(ss[f[i][j]],Nd,tc);}}
}
bool bfs()
{TAG
&#43;&#43;;Q[bot&#61;top&#61;1]&#61;t,d[t]&#61;0,tag[t]&#61;TAG,can[t]&#61;false;while (bot<&#61;top){int cur&#61;Q[bot&#43;&#43;];for (int i&#61;first[cur]; i!&#61;-1; i&#61;next[i])if (c[i^1]>0 && tag[to[i]]!&#61;TAG){tag[to[i]]&#61;TAG,Q[&#43;&#43;top]&#61;to[i],d[to[i]]&#61;d[cur]&#43;1,can[to[i]]&#61;false;if (to[i]&#61;&#61;s) return true;}}return false;
}
int dfs(int cur,int num)
{
if (cur&#61;&#61;t) return num;int tmp&#61;num,k;for (int i&#61;first[cur]; i!&#61;-1; i&#61;next[i])if (c[i]>0 && d[to[i]]&#61;&#61;d[cur]-1 && tag[to[i]]&#61;&#61;TAG && can[to[i]]&#61;&#61;false){k&#61;dfs(to[i],min(num,c[i]));if (k) num-&#61;k,c[i]-&#61;k,c[i^1]&#43;&#61;k;//if (num&#61;&#61;0) return tmp;
}if (num) can[cur]&#61;true;return tmp-num;
}
int main()
{getprim(); scanf(
"%d",&T); while (T--){scanf("%d",&n);for (int i&#61;1; i<&#61;2*n; i&#43;&#43;) scanf("%d",&a[i]),deal(i);_init();buildedge(); while (bfs()) ans&#43;&#61;dfs(s,maxn);printf("%d\n",ans);}return 0;
}

 

 

SEAEQ&#xff1a;为什么这是整场比赛通过人数最少的题目&#xff1f;我觉得在平时比赛这种难度的题目也就算中等吧&#xff1f;此题让我想去去年杭州赛的那个题。深坑呐。解法是这样的&#xff0c;dp预处理长度为i的排列有不超过j个逆序数对的情况有多少种&#xff01;这个可以dp好好想想就知道了&#xff0c;剩下的就是逆推枚举了&#xff0c;直接枚举区间长度&#xff0c;位置&#xff0c;对于两个排列其他的位置都是全排列即可。对于题目的那个要求就是在规定区间内&#xff0c;每个位置的相对大小相同即可&#xff0c;这个只需要保证对于预处理的种类数乘一次&#xff0c;对于取组合数和全排列数乘以两次即可。不难理解&#xff0c;自己想想就很清楚了。一开始取模打成了1000000009&#xff0c;都怪前几天打的那场acdream&#xff0c;坑死啦。

#include
#include

#include

#define maxn 502
typedef
long long ll;
using namespace std;const int M&#61;1000000007;
int n,e,T,ans;
int sum[maxn][(maxn*maxn-maxn)/2];//�度����对�
ll P[maxn],C[maxn][maxn];int main()
{P[
0]&#61;1,C[0][0]&#61;1;for (int i&#61;1; i1]*i)%M;for (int i&#61;1; i){C[i][0]&#61;1;for (int j&#61;1; j<&#61;i; j&#43;&#43;) C[i][j]&#61;(C[i-1][j-1]&#43;C[i-1][j])%M;}int last&#61;0,next;sum[1][0]&#61;1;for (int i&#61;2; i){next&#61;last&#43;i-1;sum[i][0]&#61;1;for (int j&#61;1; j){sum[i][j]&#61;sum[i][j-1]&#43;sum[i-1][j];if (sum[i][j]>&#61;M) sum[i][j]-&#61;M;}for (int j&#61;i; j<&#61;last; j&#43;&#43;){sum[i][j]&#61;sum[i][j-1]&#43;sum[i-1][j]-sum[i-1][j-i];if (sum[i][j]>&#61;M) sum[i][j]-&#61;M;if (sum[i][j]<0) sum[i][j]&#43;&#61;M;}for (int j&#61;last&#43;1; j<&#61;next; j&#43;&#43;){sum[i][j]&#61;sum[i][j-1]&#43;sum[i-1][last]-sum[i-1][j-i];if (sum[i][j]>&#61;M) sum[i][j]-&#61;M;if (sum[i][j]<0) sum[i][j]&#43;&#61;M;}last&#61;next;}scanf("%d",&T);while (T--){scanf("%d%d",&n,&e);ans&#61;0;for (int i&#61;1; i<&#61;n; i&#43;&#43;){int cur&#61;min((i*i-i)/2,e);cur&#61;sum[i][cur];ll tmp&#61;(C[n][i]*P[n-i])%M;tmp&#61;((tmp*tmp)%M*cur)%M;ans&#43;&#61;(tmp*(n&#43;1-i))%M;if (ans>&#61;M) ans-&#61;M;}printf("%d\n",ans);}return 0;
}

 


转载于:https://www.cnblogs.com/lochan/p/3843247.html


推荐阅读
  • 本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • 本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • 本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计,并以数字赋能和创新驱动高质量发展的理念,建设了集成、智慧、高效的一体化城市综合管理平台,促进了城市的数字化转型。该中心被称为当代城市的智能心脏,为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]
  • HDU 2372 El Dorado(DP)的最长上升子序列长度求解方法
    本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法,通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]
  • 本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]
  • c语言\n不换行,c语言printf不换行
    本文目录一览:1、C语言不换行输入2、c语言的 ... [详细]
  • 本文介绍了为什么要使用多进程处理TCP服务端,多进程的好处包括可靠性高和处理大量数据时速度快。然而,多进程不能共享进程空间,因此有一些变量不能共享。文章还提供了使用多进程实现TCP服务端的代码,并对代码进行了详细注释。 ... [详细]
  • 本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体,实现了入队和出队操作,并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]
  • 动态规划算法的基本步骤及最长递增子序列问题详解
    本文详细介绍了动态规划算法的基本步骤,包括划分阶段、选择状态、决策和状态转移方程,并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中,在以后尽可能多地利用这些子问题的解,从而提高算法的效率。 ... [详细]
  • Linux环境变量函数getenv、putenv、setenv和unsetenv详解
    本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数,可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值,并打印出来。 ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • 本文介绍了一个题目的解法,通过二分答案来解决问题,但困难在于如何进行检查。文章提供了一种逃逸方式,通过移动最慢的宿管来锁门时跑到更居中的位置,从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况,并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后,文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]
  • 本文讨论了clone的fork与pthread_create创建线程的不同之处。进程是一个指令执行流及其执行环境,其执行环境是一个系统资源的集合。在调用系统调用fork创建一个进程时,子进程只是完全复制父进程的资源,这样得到的子进程独立于父进程,具有良好的并发性。但是二者之间的通讯需要通过专门的通讯机制,另外通过fork创建子进程系统开销很大。因此,在某些情况下,使用clone或pthread_create创建线程可能更加高效。 ... [详细]
  • VScode格式化文档换行或不换行的设置方法
    本文介绍了在VScode中设置格式化文档换行或不换行的方法,包括使用插件和修改settings.json文件的内容。详细步骤为:找到settings.json文件,将其中的代码替换为指定的代码。 ... [详细]
  • 前景:当UI一个查询条件为多项选择,或录入多个条件的时候,比如查询所有名称里面包含以下动态条件,需要模糊查询里面每一项时比如是这样一个数组条件:newstring[]{兴业银行, ... [详细]
author-avatar
承诺你的慌言_153
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有