so?
T1 & T2 : zgc 114514 年前就会的题
T3 ：模拟一下，算下差然后gcd一下就能A了
T4 & T5 ：原本直接去打 H 的（一流倒打），后来发现貌似很简单，然后写 T 了。。。e 想要优化，想到二分+DP但DP那块没想出来，于是回去 K T4了。 然后哈哈哈哈哈哈我点错题了，点成T5了，秉着“lazy”（贴了一身的懒标记）的原则，将错就错，写个非常暴力的dpA了，顺手（原本思路没想太明白，后来（不信别怪我)一道光照耀在我的脑中，直接”悟“了。。。）dfs收下T4
T4
#include<bits/stdc++.h>
#define Sig signed
#define uSig unsigned
using namespace std;
typedef long long ll;
inline int read()
{
int p=0,q=1;
char ch=getchar();
while(!isdigit(ch)) q=(ch=='-')?-1:1,ch=getchar();
while(isdigit(ch)) p=(p<<3)+(p<<1)+(ch^48),ch=getchar();
return p*q;
}
int n,A,B,C,a[20],ans=INT_MAX;
struct Student
{
int ws,top;
}as,bs,cs;
void dfs(int ks,int steps)
{
if(ks==n)
{
if(as.ws&&bs.ws&&cs.ws)
{
steps+=abs(A-as.ws);
steps+=abs(B-bs.ws);
steps+=abs(C-cs.ws);
ans=min(ans,steps);
}
return;
}
ks++;
dfs(ks,steps);
as.ws+=a[ks];
as.top++;
if(as.top>=2)
dfs(ks,steps+10);
else
dfs(ks,steps);
as.top--;
as.ws-=a[ks];
bs.top++;
bs.ws+=a[ks];
if(bs.top>=2)
dfs(ks,steps+10);
else
dfs(ks,steps);
bs.top--;
bs.ws-=a[ks];
cs.top++;
cs.ws+=a[ks];
if(cs.top>=2)
dfs(ks,steps+10);
else
dfs(ks,steps);
cs.top--;
cs.ws-=a[ks];
}
Sig main(void)
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
cin>>A>>B>>C;
for(int i=1;i<=n;i++) cin>>a[i];
dfs(0,0);
cout<<ans;
return 0;
}
T5
#include<bits/stdc++.h>
#define Sig signed
#define uSig unsigned
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);++(i))
using namespace std;
typedef long long ll;
const int inf=1e6+10;
int n,ans;
int a[110][110];
int s[inf<<1];
Sig main(void)
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
scanf("%d",&n);
fup(i,1,n) fup(j,1,n) scanf("%d",&a[i][j]);
fup(i,1,n) fup(j,1,n) a[i][j]=a[i][j]+a[i][j-1]+a[i-1][j]-a[i-1][j-1];
fup(i,1,n) fup(j,1,n)
{
fup(x,1,i) fup(y,1,j) ++s[a[i][j]-a[i][y-1]-a[x-1][j]+a[x-1][y-1]+inf];
fup(x,i+1,n) fup(y,j+1,n) ans+=s[a[x][y]-a[i][y]-a[x][j]+a[i][j]+inf];
fup(x,1,i) fup(y,1,j) --s[a[i][j]-a[i][y-1]-a[x-1][j]+a[x-1][y-1]+inf];
fup(x,1,i) fup(y,j+1,n) ++s[a[i][y]-a[x-1][y]-a[i][j]+a[x-1][j]+inf];
fup(x,i+1,n) fup(y,1,j) ans+=s[a[x][j]-a[i][j]-a[x][y-1]+a[i][y-1]+inf];
fup(x,1,i) fup(y,j+1,n) --s[a[i][y]-a[x-1][y]-a[i][j]+a[x-1][j]+inf];
}
printf("%d\n",ans);
return 0;
}
hhT6 : 群魔乱舞？？？（事先声明：以下并无冒犯任何人）
超级有实力的（zhayu+dalao）：3s一个2100，A了！！！
乱打&有实力的：hh这么简单，（命好多捡10分）
正经打&有实力的：hh为啥人家乱打六七十分，我才20几？？？
正经打&。。。：偷5分，命好多偷10分
不正经打&。。。：准备好0吧
but 我：95：TLE
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
心态炸裂
有时候因为小细节没A，但又不甘心跳下一题。 ——cjx
准备摸鱼。。。
T6 AC Code
#include <bits/stdc++.h>
#define Sig signed
#define uSig unsigned
#define fup(i, a, b) for (int(i) = (a); (i) <= (b); ++(i))
#define fdown(i, a, b) for (int(i) = (a); (i) >= (b); --(i))
#define Vt vector
#define Pq priority_queue
#define pb push_back
#define ps push
#define Il inline
using namespace std;
typedef long long ll;
const int N = 2e3 + 10, inf = 0x3f3f3f3f;
int n;
int voted[N], cost[N];
Vt<int> V[N];
int ans = 1e9, res, cnt;
Il int read() {
int p = 0, q = 1;
char ch = getchar();
while (!isdigit(ch)) q = (ch == '-') ? -1 : 1, ch = getchar();
while (isdigit(ch)) p = (p << 3) + (p << 1) + (ch ^ 48), ch = getchar();
return p * q;
}
void init() { res = 0, cnt = V[1].size(); }
Sig main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
n = read();
fup(i, 2, n) voted[i] = read();
fup(i, 2, n) cost[i] = read(), V[voted[i]].push_back(cost[i]);
fup(i, 1, n) sort(V[i].begin(), V[i].end());
fup(i, V[1].size(), n) {
Pq<int, Vt<int>, greater<int> > pq;
init();
fup(j, 2, n) {
int vjs = V[j].size();
if (i <= vjs) {
fup(k, 0, vjs - 1) {
if (k <= vjs - i)
res += V[j][k], cnt++;
else
pq.ps(V[j][k]);
}
} else
fup(k, 0, vjs - 1) pq.ps(V[j][k]);
}
fup(j, 1, i - cnt) res += pq.top(), pq.pop();
ans = min(ans, res);
}
printf("%d\n", ans);
system("pause");
return 0;
}
最快是 n log n 吧，qr？
摸鱼时间到