有幸能够参加有这么多优秀队伍的比赛，确实也通过这个看出了自身很多的不足，无论是浙江高校还是浙江的高中生，他们的训练水平还是远远在我们之上的。唯有好好努力，才能创造机会。
I-Little Sub and Triangles 题意很简单，就是给出了一堆平面上的格点，每次询问会给一个范围，问落在这个范围里面的由这些格点组成的三角形的数量是多少。
首先先想到求出所有的三角形，然后再排序。排序之后的每次查询只要二分就可以了。
但是这道题要注意的地方有：
1.给出了三个点求三角形的面积用向量的叉积是比较方便的。两个向量分别是(x1,y1)，(x2,y2)的时候，向量叉积是x1y2-y1x2。而用sqrt的效率比较低，这里会超时。
2.格点三角形一定是1/2的整数倍，因为不妨把这个三角形补全，你很快就会发现多出来的三角形一定是1/2的整数倍。所以这里如果让所有的数都乘上2，这道题就转化为了全整数的问题，就便于处理了。
#pragma GCC optimize(3,"Ofast","inline")
#include
#define pb push_back
#define Rep(i,a,b) for(int i=a;
i<=b;
i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf=0x3f3f3f3f;
const ll INF=9e18;
const int N=300;
int cnt=0;
ll tri[N*N*N],x[N],y[N];
int main() {
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;
i<=n;
i++) scanf("%lld%lld",&x[i],&y[i]);
for(int i=1;
i<=n;
i++)
for(int j=i+1;
j<=n;
j++)
for(int k=j+1;
k<=n;
k++)
tri[++cnt]=abs((x[j]-x[i])*(y[k]-y[i])-(y[j]-y[i])*(x[k]-x[i]));
sort(tri+1,tri+cnt+1);
while(q--) {
ll l,r;
scanf("%lld%lld",&l,&r);
l*=2,r*=2;
int pl=lower_bound(tri+1,tri+cnt+1,l)-tri;
int pr=upper_bound(tri+1,tri+cnt+1,r)-tri;
printf("%d\n",pr-pl);
}
return 0;
}
H-Little Sub and Counting 题意说给出一些数，然后要求出对于每个给定的数x，满足 x y > y x x^{y}> y^{x} xy>yx的
的数目的。然后这个题考虑变成 x l n x \frac{x}{lnx} lnxx?求导，然后我们容易发现 e e e是它的一个极值点，只需要特判一下前面的1,2,3，然后对后面的数直接二分找到第一个大于它们的数就可以了。
需要注意的是如何写好一个结构体的二分，结构体的二分比较的一定是一个结构体，需要写构造函数放进去二分。
1#pragma GCC optimize(3,"Ofast","inline")
#include
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=LONG_LONG_MAX;
const int N=1e5+50;
struct node{
int x,id,ans;
node() {}
node(int x,int id=0,int ans=0):x(x),id(id),ans(ans) {}
bool operator <(const node& rhs) const {
return x B-Little Sub and Triples 【2019杭州师范大学校赛】这道题是给我印象最深的一道题，题意其实化简一下就是说对于一个数组，每次都会去询问一段区间，然后问这个区间是否可以存在三个数，它们能够构成三角形。先考虑对区间排序。那么对于这个每个数，只要考虑最大的比它小的那两个数是否大于它就可以了。但是每次都对区间排序的话，这个复杂度会非常大。这里需要逆向思考这个问题，如果这个区间是NO的话，但是要保证里面的所有的数字都尽量小，那么这个区间实际上就是一个Fibonacci数列，而Fibonacci数列很快就会增长超过int的范围。所以说对于长度超过60的区间，直接就可以判断是YES，对于剩下来的情况再做排序处理就好了。
这里的逆向思考的思维确实很精妙。
#pragma GCC optimize(3,"Ofast","inline")
#include
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=LONG_LONG_MAX;
const int N=2e5+50;
int a[N];
vector v;
int main() {
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;
i<=n;
i++) scanf("%d",&a[i]);
while(q--) {
int l,r;
scanf("%d%d",&l,&r);
if(r-l+1<=2) printf("NO\n");
else if(r-l+1>=60) printf("YES\n");
else {
v.clear();
for(int i=l;
i<=r;
i++) v.push_back(a[i]);
sort(v.begin(),v.end());
bool exist=false;
for(int i=0;
iv[i+2]-v[i+1]) { exist=true;
break;
}
}
if(exist) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
E-Little Sub and Traveling 这道题是一个非常有想法的题目。位置从0开始。然后每次都可以转移自己的位置 i i i，要么转移为 2 ? i + 1 m o d n 2*i+1mod n 2?i+1modn，要么转移为 2 ? i m o d n 2*imod n 2?imodn。要求字典序最大的汉密尔顿回路。首先对于奇数的情况是无解的，证明是这样的：不妨设 n = 2 ? k + 1 n=2*k+1 n=2?k+1，1.最终要回到0，必须要通过k转移。2 . 2 k 2k 2k 这个数也只能通过k k k 来转移。3.第一次走到 k k k的时候，若直接返回，则 2 k 2k 2k没有被走过。若走到 2 k 2k 2k则无法再回到0，因为必须要从 k k k返回，但是 k k k已经被走过一次。所以综上所述。奇数是无解的。那么考虑偶数的构造。主要这模n运算对 i i i和 i + n / 2 i+n/2 i+n/2是完全等价的。不妨把这两个点并成一个点。这样每个点都有两个入度和两个出度。而这恰好就是一个欧拉回路。在欧拉回路上做一遍逆序dfs。
#pragma GCC optimize(3,"Ofast","inline")
#include
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=LONG_LONG_MAX;
const int N=1e4+50;
bool vis[N];
int n;
vector ans;
void dfs(int now) {
if(!vis[(2*now+1)%n]) {
vis[(2*now+1)%n]=1;
dfs((2*now+1)%(n/2));
ans.push_back((2*now+1)%n);
}
if(!vis[(2*now)%n]) {
vis[(2*now)%n]=1;
dfs((2*now)%(n/2));
ans.push_back((2*now)%n);
}
}
int main() {
scanf("%d",&n);
if(n&1) { puts("-1");
return 0;
}
else {
vis[0]=1;
ans.push_back(0);
dfs(0);
ans.push_back(0);
}
for(int i=ans.size()-1;
i>=0;
i--)
printf("%d%c",ans[i],i==0?'\n':' ');
return 0;
I-Little Sub and Enigma 这道题在场上并没有读懂题意，其实是要求S和T满足一个双射，如果可以满足就输出全部的映射。首先先维护S串中的每个字符不能指向两个不同的字符，然后再维护T串每个字符也不能被两个不同的字符所指。
但是这道题需要注意的事情就是当你确定了25组关系的时候，剩下来的那一组也会被唯一确定，这种情况需要特判。
#pragma GCC optimize(3,"Ofast","inline")
#include
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=LONG_LONG_MAX;
const int N=1e6+50;
char s1[N],s2[N];
int a[200],b[200];
int main() {
int cnt=0;
scanf("%s%s",s1+1,s2+1);
int len=strlen(s1+1);
for(int i=1;
i<=len;
i++) {
if(!a[s1[i]]) a[s1[i]]=s2[i],++cnt;
else if(a[s1[i]]&&a[s1[i]]!=s2[i]) return 0*printf("Impossible\n");
}
for(int i=1;
i<=len;
i++) {
if(!b[s2[i]]) b[s2[i]]=s1[i];
else if(b[s2[i]]&&b[s2[i]]!=s1[i]) return 0*printf("Impossible\n");
}
if(cnt==25)
for(int i='a';
i<='z';
i++)
for(int j='a';
j<='z';
j++){
if(!a[i]&&!b[j]) a[i]=j;
}
for(int i='a';
i<='z';
i++) {
if(a[i]) printf("%c->%c\n",(char)i,(char)a[i]);
}
return 0;
}
M-Little Sub and Johann 这个是一个挺好的博弈题，其实只要好好找规律很快就能发现规律。对于石子个数只有1的堆SG为1，然后对于质数SG是这个质数在质数表里面的位置+1，对于合数SG是它的最小质因子。恰好可以用线筛筛出来所有范围内的SG函数。
接下来证明一下这个SG函数。对于石子个数为1是显然的。而质数则是由前面所有的状态转移，因此是连续单调递增的。然后考虑一个合数所有被转移的情况，是从0到最小质因数-1，然后这些质数的SG函数都是连续增加的，所以第一个无法被转移到的位置就是最小质因数，所以就是SG[lPF]
其实不是一道很难的题，所以还是姿势水平不太够。
#pragma GCC optimize(3,"Ofast","inline")
#include
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=LONG_LONG_MAX;
const int N=1e6+5;
int pri[N],sg[N],cnt=0;
bool vis[N];
void getsg() {
sg[1]=1;
for(int i=2;
i<=(int)1e6;
i++) {
if(!vis[i]) pri[++cnt]=i,sg[i]=cnt+1;
for(int j=1;
j<=cnt&&i*pri[j]<=(int)1e6;
j++) {
vis[i*pri[j]]=true;
sg[i*pri[j]]=sg[pri[j]];
if(i%pri[j]==0) break;
}
}
}
int main() {
getsg();
int line;
scanf("%d",&line);
while(line--) {
int n,ans=0;
scanf("%d",&n);
for(int x,i=1;
i<=n;
i++) scanf("%d",&x),ans^=sg[x];
if(!ans) printf("Long live with King Johann!\n");
else printf("Subconscious is our king!\n");
}
return 0;
}
G-Little Sub and Piggybank 这是一道非常有趣的dp题，可以学习让我们学习到不少东西。题意是说每个商品都有一个价格，并且每个商品都能带来一定的快乐值，然后每个时刻都可以投入任意多数量的钱，但是必须要保证后面投入的不能超过前面投入的钱，而且买任何商品都必须是刚刚好这个商品价格的钱数才能购买。
首先贪心考虑如果我要买的商品是 a k 1 , a k 2 . . . a k m a_{k_{1}},a_{k_{2}}...a_{k_{m}} ak1??,ak2??...akm??,那么最优的做法应该是在中间的每一天都购买 a k 2 ? a k 1 / k 2 ? k 1 a_{k_{2}}-a_{k_{1}}/k_{2}-k_{1} ak2???ak1??/k2??k1?。记dp[i][j]是我最后一个买的商品是i，倒数第二个买的商品是j的最大值，dp[i][j]=max(dp[i][j],dp[j][k]+v[i])，这里k<=j<=i。然后由于满足条件，a[i]/(i-j)<=a[j]/(j-k)，化简一下就可以分离k使得k>=j-a[j]/a[i]*(i-j)，这里每次处理出来dp[i][j]以后都可以处理出g[i][j]=max{dp[i][i-1]…dp[i][j]}，这样复杂度就可以被优化到O(n^2)。
1.转移的时候不仅要保证k
#pragma GCC optimize(3,"Ofast","inline")
#include
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=LONG_LONG_MAX;
const int N=2e3+50;
int a[N],v[N],f[N][N],g[N][N];
int main() {
int n,k;
scanf("%d",&n);
for(int i=1;
i<=n;
i++) scanf("%d",&a[i]);
for(int i=1;
i<=n;
i++) scanf("%d",&v[i]);
for(int i=1;
i<=n;
i++) {
f[i][0]=v[i];
for(int j=1;
j=0;
j--) {
g[i][j]=max(g[i][j+1],f[i][j]);
}
}
int ans=0;
for(int i=1;
i<=n;
i++) ans=max(ans,g[i][0]);
printf("%d\n",ans);
return 0;
}
