感觉这套比赛题目比较容易,没有以前做过的某次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
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
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;
}