1802

cjyasleep

Kellon

taozhiming
silence_91

RSqwq

Gesture_nzq

Rabilista

NNNN-----IIII
lwt_3
Kazimierz

11小时前

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 510;
int s[N][N], k, n, m;
int main(){
cin>>n>>m>>k;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d", &s[i][j]), s[i][j] += s[i-1][j];//求每一列的前缀和
LL res=0;
for(int i=1; i<=n; i++){//上边界i
for(int j=i; j<=n; j++){//下边界j
for(int l=1, r=1, sum=0; r<=m; r++){//二分
sum += s[j][r] - s[i-1][r];
while(l<=r && sum>k){
sum -= s[j][l] - s[i-1][l];
l++;
}
res += r - l + 1;
}
}
}
cout<<res<<endl;
return 0;
}


bilibi

s[i]至少的贡献值为1（它本身），至多到上一次出现s[i]位置之间的元素个数，即i - lta[s[i]]
f[i]=f[i−1]+i−pos

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
//lta[i]表示s[i]上一次出现的位置
//f[i]表示以s[i]为结尾的所有子串的总分值
int lta[200], f[N];
string s;
int main()
{
cin>>s;
s = ' ' + s;
int len = s.size();
LL res = 0;
for(int i=1; i<len; i++){
f[i] = f[i-1] + i - lta[s[i]];
lta[s[i]] = i;
res += f[i];
}
cout<<res<<endl;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
string date;

bool check_year(int year){//判断闰年
return year % 400 == 0 || year % 4 == 0 && year % 100 != 0;
}

bool check(string s, int year){//判断回文日期和ABABBABA型的日期合法性
string month = s.substr(0,2);
int m = stoi(month);
string day = s.substr(2,4);
int d = stoi(day);

if(m == 2){
if(check_year(year))
return m >= 1 && m <=12 && d >= 1 && d <= months[m]+1;
else return m >= 1 && m <=12 && d >= 1 && d <= months[m];
}else return m >= 1 && m <=12 && d >= 1 && d <= months[m];
}

int main()
{
cin>>date;
string cur_y = date.substr(0,4);
string cur_md = date.substr(4,8);
bool st1 = false, st2 = false;
for(int i=stoi(cur_y); i<=9999; i++){
string s1 = to_string(i);
string s2;
for(int j=s1.size()-1; j>=0; j--) s2.push_back(s1[j]);
if(s1+s2 <= date) continue;//卡
if(check(s2, i) && !st1){
st1 = true;
cout<<s1 + s2<<endl;
}
if(s1[0] == s1[2] && s1[1] == s1[3] &&
s1[0] != s1[1] && check(s2, i) && !st2){
st2 = true;
cout<<s1 + s2<<endl;
break;
}
}
return 0;
}


A 市的车牌由六位组成, 其中前三位可能为数字 0 至 9 , 或者字母 AA 至 FF, 每位有 16 种可能。后三位只能是数字 0 至 9。为了减少攀比, 车牌中不能有连 续三位是相同的字符。

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int cnt;
void dfs(int n){
if(n == 6){
bool flag = false;
for(int i=0; i+2<v.size(); i++){
if(v[i] == v[i+1] && v[i] == v[i+2]){
flag = true;
break;
}
}
if(!flag) cnt++;
}
else{
int k = n < 3 ? 15 : 9;
for(int i=0; i<=k; i++){
v.push_back(i);
dfs(n+1);
v.pop_back();
}
}
}
int main(){
dfs(0);
cout<<cnt<<endl;
return 0;
}


最小的 5 个 Fibonacci 数 1, 2, 3, 5, 8 属于集合 F。



//priority_queue<ll , vector<ll> , greater<ll> > mn; 小根堆 小到大
//priority_queue<ll , vector<ll> , less<ll> > mx; 大根堆 大到小
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
typedef long long LL;
priority_queue<LL, vector<LL>, greater<LL>> q;
unordered_map<LL,bool> m;
int a[2040], idx;
int main()
{
int cnt = 0;
q.push(1); m[1] = true;
q.push(2); m[2] = true;
q.push(3); m[3] = true;
q.push(5); m[5] = true;
q.push(8); m[8] = true;
while(!q.empty()){
cnt++;
LL x = q.top();
q.pop();
if(cnt == 2020){
cout<<x<<endl;
break;
}
LL w[] = {3 * x + 2, 5 * x + 3, 8 * x + 5};
for(int i=0; i<3; i++){
if(!m[w[i]]){
m[w[i]] = true;
q.push(w[i]);
}
}

}
return 0;
}


#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], ans, n;

int gcd(int a, int b){
return b ? gcd(b, a%b) : a;
}

int main()
{
cin>>n;
for(int i=0; i<n; i++) cin>>a[i];
sort(a, a+n);
int t = 0;
for(int i=0; i+1<n ;i++) t = gcd(t, a[i+1] - a[i]);
if(!t) cout<<n<<endl;
else cout<<(a[n-1] - a[0]) / t + 1<<endl;
return 0;
}


#include <iostream>
using namespace std;
const int N = 10;
int e[N][N], p[N], ans;
bool st[N];//true表示第i盏灯亮

void init(){
e[1][2] = e[1][6] = 1;
e[2][1] = e[2][7] = e[2][3] = 1;
e[3][2] = e[3][7] = e[3][4] = 1;
e[4][3] = e[4][5] = 1;
e[5][4] = e[5][7] = e[5][6] = 1;
e[6][1] = e[6][7] = e[6][5] = 1;
e[7][2] = e[7][3] = e[7][5] = e[7][6] = 1;
}

int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}

void dfs(int n){
if(n>7){
for(int i=1; i<=7; i++) p[i] = i;
for(int i=1; i<=7; i++)//将所有亮的灯做连通合并
for(int j=1; j<=7; j++)
if(e[i][j] == 1 && st[i] && st[j])
p[find(i)] = find(j);
int cnt = 0;
for(int i=1; i<=7; i++){//遍历所有亮着的灯是否只与同一个灯连通
if(st[i] && p[i] == i)
cnt++;
}
if(cnt == 1) ans++;
return;
}
st[n] = true;
dfs(n+1);
st[n] = false;
dfs(n+1);
}

int main()
{
init();
dfs(1);
cout<<ans<<endl;
return 0;
}


#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;

int n, m, a[N], ans=N, sum[N];//sum[i]第i辆车

bool cmp(int a, int b){
return a>b;
}

void dfs(int x, int k){//a[x]表示第x个小猫的重量，k表示第k辆车
if(k >= ans) return;
if(x == n){
ans = k;
return;
}
for(int i=0; i<k; i++){//判断a[x]能放进前k-1辆车的哪一台车
if(a[x] + sum[i] <= m ){
sum[i] += a[x];
dfs(x+1, k);
sum[i] -= a[x];//恢复现场
}
}
//新加一台车放进去
sum[k] = a[x];
dfs(x+1, k+1);
sum[k] = 0;//恢复现场
}

int main()
{
cin>>n>>m;
for(int i=0; i<n; i++) cin>>a[i];
sort(a, a+n, cmp);
dfs(0, 0);
cout<<ans;
return 0;
}


#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;

int n, m, a[N], ans=N, sum[N];//sum[i]第i辆车

bool cmp(int a, int b){
return a>b;
}

void dfs(int x, int k){//a[x]表示第x个小猫的重量，k表示第k辆车
if(k >= ans) return;
if(x == n){
ans = k;
return;
}
for(int i=0; i<k; i++){//判断a[x]能放进前k-1辆车的哪一台车
if(a[x] + sum[i] <= m ){
sum[i] += a[x];
dfs(x+1, k);
sum[i] -= a[x];//恢复现场
}
}
//新加一台车放进去
sum[k] = a[x];
dfs(x+1, k+1);
sum[k] = 0;//恢复现场
}

int main()
{
cin>>n>>m;
for(int i=0; i<n; i++) cin>>a[i];
sort(a, a+n, cmp);
dfs(0, 0);
cout<<ans;
return 0;
}


#include <iostream>
#include <unordered_set>
using namespace std;

const int N = 10, M = 10;
int a[N][M], n, m, k, dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1};// 上左下右
unordered_set<int> s;

void dfs(int i, int j, int d, int num){
if(d == k){
s.insert(num);
return;
}
for(int k=0; k<4; k++){
int x = i + dx[k], y = j + dy[k];
if(x >= 0 && x < n && y >= 0 && y < m)
dfs(x, y, d+1, num*10+a[x][y]);
}
}

int main()
{
cin>>n>>m>>k;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin>>a[i][j];

for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
dfs(i, j, 0, a[i][j]);
}
}
cout<<s.size();
return 0;
}