D1T1
对于一个格点图，类似于男人八题T1，我们这道题也可以先找出矩形，之后再找出不是矩形的 平行四边形。 0 0 0 0 0 0 0 0 0 0 我们采取上次同样的策略来找，发现规律： S = (3 + 2 + 1) (2 + 1) 1 (1 + 2) (1 + 2 + 3) 怎么总结呢？ 我们发现：其实就是1 * n + ... + n * n - 2 - 6 - 12- ...我们再次发现（我们好厉害） 后面减去的那一坨其实就是2 * (S的一半） ok 再加上之前的矩形 规律为:(2n + 1)n(n + 1)/6
D1T2
对于这道题的话其实出题人已经很良心了，在输入的时候提示了，很容易想到折半搜索，
因为我们发现对于每个颜色的数量一定为n所以当我们在前半个n找出了p个的某个颜色，那么
这个某个颜色在另外的区间一定有n - p个，那么我们怎么统计合法方案呢？hash！！！
我们现在已经开始统计后半个区间，如果合法那么当前颜色的总hash值一定会有前半个的另外一个颜色的总hash值和它相等
//挂题原因
不会用map，实际上它很简单呢！！
//可爱的小分割线
code:
#include<cstdio>
#include<iostream>
#include<map>
#define ll long long
using namespace std;
const long long mod = 1e18 + 17;
map<ll,int>res[100];
long long ans,d[100];
int n,p,q;
char c[100];
void dfs1(int u,ll col)
{
if(u == n + 1)
{
//cout << col << endl;
res[p][col]++;
return;
}
ll x;
p++;
x = (col + d[p] * (c[u] - 'a' + 1)) % mod;
dfs1(u + 1,x);
p--;
q++;
x = (col - d[q] * (c[u] - 'a' + 1)) % mod;
dfs1(u + 1,x);
q--;
}
void dfs2(int u,ll col)
{
if(u == n)
{
//cout << col << endl;
ans += res[q][col];
return;
}
ll x;
p++;
x = (col - d[p] * (c[u] - 'a' + 1)) % mod;
dfs2(u - 1,x);
p--;
q++;
x = (col + d[q] * (c[u] - 'a' + 1)) % mod;
dfs2(u - 1,x);
q--;
}
int main()
{
cin >> n;
scanf("%s",c + 1);
d[1] = 31;
for(int i = 2;i <= n;i += 1)
d[i] = d[i - 1] * 31 % mod;
dfs1(1,0);
//cout << endl;
dfs2(2 * n,0);
cout << ans << endl;
return 0;
}D1T3
聪聪叹气，审题是个好东西，对于这个题我们发现统计内含整点个数，其实就是找到这个三角形
为什么呢？因为我们有公式S = a + b/2 - 1，那么出题人还要求锐角三角形，可我们还有
a ^ 2 + b ^ 2 > c ^ 2（我们有的挺多）这样的话我们就把问题转化成立找三角形问题，
怎么找呢，三元环计数！三元环做法详解直接上链接
https://www.cnblogs.com/Dance-Of-Faith/p/9759794.html
注意重边的代价要翻倍毕竟一个三元环的度位2,1,0
b咋算？？getgcd！
OK完美
//挂题原因
审题失误以为相交边不会产生影响，并且我还不会三元环（我好菜娅），甚至还不会map
虽然我现在还是没A，不过还是感觉进步了，dalao看看否哪里WA了>嘤嘤嘤
//我是分割线
#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 3e5 + 17;
const int mod = 998244353;
struct node
{
int v,next;
}e[MAXN];
map<int,map<int,int> >q;
map<int,map<int,int> >w;
map<int,map<int,double> >d;
map<int,map<int,int> > h;
int tot,top,head[MAXN],vis[MAXN],a1[MAXN],a2[MAXN],b1[MAXN],b2[MAXN],in[MAXN];
int getgcd(int a,int b)
{
if(a < b)swap(a,b);
if(b == 0)return a;
return getgcd(b,a % b);
}
long long gets(double x,double y,double z)
{
double p = (x + y + z) / 2;
return sqrt(p * (p - x) * (p - y) * (p - z));
}
void add(int u,int v)
{
e[++tot].v = v;
e[tot].next = head[u];
head[u] = tot;
}
bool rui(int x,int y,int z)
{
if(x * x + y * y <= z * z)return 0;
if(x * x + z * z <= y * y)return 0;
if(y * y + z * z <= x * x)return 0;
return 1;
}
double getd(double x,double y)
{
return sqrt(x * x + y * y);
}
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i += 1)
{
cin >> a1[i] >> b1[i] >> a2[i] >> b2[i];
if(!q[a1[i]][b1[i]])q[a1[i]][b1[i]] = ++top;
if(!q[a2[i]][b2[i]])q[a2[i]][b2[i]] = ++top;
w[q[a1[i]][b1[i]]][q[a2[i]][b2[i]]] = w[q[a2[i]][b2[i]]][q[a1[i]][b1[i]]] = getgcd(abs(a2[i] - a1[i]),abs(b2[i] - b1[i]));
d[q[a1[i]][b1[i]]][q[a2[i]][b2[i]]] = d[q[a2[i]][b2[i]]][q[a1[i]][b1[i]]] = getd(abs(a2[i] - a1[i]),abs(b2[i] - b1[i]));
in[q[a1[i]][b1[i]]]++;
in[q[a2[i]][b2[i]]]++;
}
for(int i = 1;i <= n;i += 1)
{
if(h[q[a1[i]][b1[i]]][q[a2[i]][b2[i]]])
{
h[q[a1[i]][b1[i]]][q[a2[i]][b2[i]]]++;
h[q[a2[i]][b2[i]]][q[a1[i]][b1[i]]] = h[q[a1[i]][b1[i]]][q[a2[i]][b2[i]]] ;
//w[q[a1[i]][b1[i]]][q[a2[i]][b2[i]]] = w[q[a2[i]][b2[i]]][q[a1[i]][b1[i]]] = w[q[a1[i]][b1[i]]][q[a2[i]][b2[i]]] + h[q[a1[i]][b1[i]]][q[a2[i]][b2[i]]];
continue;
}
if(in[q[a1[i]][b1[i]]] < in[q[a2[i]][b2[i]]])
add(q[a2[i]][b2[i]],q[a1[i]][b1[i]]);
if(in[q[a1[i]][b1[i]]] > in[q[a2[i]][b2[i]]])add(q[a1[i]][b1[i]],q[a2[i]][b2[i]]);
if(in[q[a1[i]][b1[i]]] == in[q[a2[i]][b2[i]]] && q[a1[i]][b1[i]] < q[a2[i]][b2[i]])
add(q[a1[i]][b1[i]],q[a2[i]][b2[i]]);
if(in[q[a1[i]][b1[i]]] == in[q[a2[i]][b2[i]]] && q[a2[i]][b2[i]] < q[a1[i]][b1[i]])
add(q[a2[i]][b2[i]],q[a1[i]][b1[i]]);
h[q[a1[i]][b1[i]]][q[a2[i]][b2[i]]] = h[q[a2[i]][b2[i]]][q[a1[i]][b1[i]]] = 1;
}
long long ans = 0;
for(int k = 1;k <= n;k += 1)
{
for(int i = head[k];i;i = e[i].next)
{
int v = e[i].v;
vis[v] = k;
}
for(int i = head[k];i;i = e[i].next)
{
int v = e[i].v;
for(int r = head[v];r;r = e[r].next)
{
int u = e[r].v;
//cout << k << v << u << endl;
if(vis[u] == k)
{
if(!rui(d[k][v],d[v][u],d[k][u]))continue;
long long s = gets(d[k][v],d[v][u],d[k][u]);
ans += (s - (w[k][v] + w[v][u] + w[k][u]) / 2 + 1) * h[k][u] * h[k][v] * h[v][u];
ans %= mod;
}
}
}
}
cout << ans << endl;
return 0;
}D2T1
问题转化，求出一种方案使得这个新图存在一个环并且所有点联通，我们再把问题细化， 所有点联通是个啥！最小生成树！咋样存在环？连一条不在树中最小边！！！ //挂题原因 小字没看见呜呜呜呜（论我到底有多粗心） //没有存在感的分割线 code: 代码搁机房了嘤嘤嘤
D2T2
满分算法还没搞懂（待更新）
D2T3
现场，聪聪贪心拿了40，但是正解的贪心还没调出来（待更新，可能是我菜了吧）
京公网安备 11010502036488号